perm filename V2P.IN[TEX,DEK] blob
sn#360779 filedate 1977-05-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 687 galley 1
C00019 00003 folio 690 galley 2
C00034 00004 folio 693 galley 3
C00050 00005 folio 701 galley 4
C00064 00006 folio 707 galley 5
C00079 00007 folio 710 galley 6
C00093 00008 folio 715 galley 7
C00107 00009 folio 717 galley 8
C00121 00010 folio 720 galley 9
C00134 00011 folio 722 galley 10
C00144 ENDMK
C⊗;
folio 687 galley 1
0 {U0}{H10L12M29}W58320#Computer Programming|9(Knuth/Addison-W
1 esley)|9f. 687|9answers|9g. 1a|'{A6}{H9L11}|πThe
5 value for a truly random sequence is |εe|4α_↓|41;
13 |πour value is |εe|4α_↓|41|4α+↓|4(e/2|4α_↓|41)/a|4α+↓|4O(1/a
16 |g2). Note|*/: |\|πThe same result holds for an
24 ascending run, since |εU|βn|4|¬R|4U|βn|βα+↓|β1
28 |πif and only if |ε1|4α_↓|4U|βn|4|¬W|41|4α_↓|4U|βn|βα+↓|β1.
33 |πThis would lead us to suspect that run lengths
42 in linear congruential dequences tend to be slightly
50 longer than normal, so the run test should be
59 applied to such generators.|'{A3}|≡2|≡5|≡.|9|4|πLet
64 |εk|β0|4α=↓|4|"pa|≤a|4α+↓|4|≤U|4α_↓|4|≤b|¬S|"P,
65 k|β1|4α=↓|4|"pa|≤b|4α+↓|4|≤U|4α_↓|4|≤b|¬S|"P.
66 x |πmust be in the intervals [(|εk|4α+↓|4|≤a|¬S|4α_↓|4|≤U)/a
72 , (k|4α+↓|4|≤b|¬S|4α_↓|4|≤U)/a) |πfor some |εk,
77 |πand also in the interval [|ε|≤a,|4|≤b). |πWith
84 due regard to boundary conditions, we get the
92 probability|'{A9}{M29}(|εk|β1|4α_↓|4k|β0)(|≤b|¬S|4α_↓|4|≤a|¬
93 S)/a|4α+↓|4|πmax{H12}({H9}0,|4|ε|≤b|4α_↓|4(k|β1|4α+↓|4|≤a|¬S
93 |4α_↓|4|≤U)/a{H12}){H10}|4α_↓|4|πmax{H11}({H9}|ε0,|4|≤a|4α_↓
93 |4(k|β0|4α+↓|4|≤a|¬S|4α_↓|4|≤U)/a{H12}){H9}.|'
94 {A9}{M29}|πThis is (|ε|≤b|4α_↓|4|≤a)(|≤b|¬S|4α_↓|4|≤a|¬S)|4α
96 +↓|4|≤e, |πwhere |¬G|ε|≤e|¬G|4|¬W|42(|≤b|¬S|4α_↓|4|≤a|¬S)/a.
98 |'{A6}{M12.6}|π|≡F|≡i|≡g|≡.|4|4|≡A|≡<|≡1|≡.|9|4Permutation
100 regions for Fibonacci generator.|'{A6}|≡F|≡i|≡g|≡.|4|4|≡A|≡<
104 |≡2|≡.|9|4Run-length regions for Fibonacci generator.|'
109 {A6}{M29}|≡2|≡6|≡.|9|4See Fig. A<1; the orderings
114 |εU|β1|4|¬W|4U|β3|4|¬W|4U|β2 |πand |εU|β2|4|¬W|4U|β3|4|¬W|4U
116 |β1 |πare impossible; the other four each have
124 probability |f1|d34|).|'{A3}|≡2|≡7|≡.|9|4|εU|βn|4α=↓|4(F|βn|
126 βα_↓|β1U|β0|4α+↓|4F|βnU|β1)|πmod 1. We need |εF|βk|βα_↓|β1U|
130 β0|4α+↓|4F|βkU|β1|4|¬W|41 |πand |εF|βkU|β0|4α+↓|4F|βk|βα+↓|β
132 1U|β1|4|¬Q|41. |πThe half-unit-square in whihc
137 |εU|β0|4|¬Q|4U|β1 |πis broken up as shown in
144 Fig. A<2, with various values of |εk |πindicated.
152 The probability for a run of length |εk |πis
161 |f1|d32|) if |εk|4α=↓|41; 1/F|βk|βα_↓|β1F|βk|βα+↓|β1|4α_↓|41
164 /F|βkF|βk|βα+↓|ε|β2, |πif |εk|4|¬Q|41. |πThe
168 corresponding probabilities for a random sequence
174 are |ε2k(k||L!!!!!!!|εk:|L1|L|32|L|33|L|74|L|5|55>
176 {A2}|L|πProbability|6in|6Fibonacci|6case:|L|f1|d32|)|L|4|f1|
176 d33|)|L|f1|d310|)|L|4|f1|d324|)|L|4|4|f1|d365|)>
177 |LProbability|6in|6random|6case:|L|f1|d33|)|L|f5|d312|)|L|f1
177 1|d360|)|L|f19|d3360|)|L|f29|d32520|)>{A9}|≡2|≡8|≡.|9|4Fig.
179 A<3 shows the various regions in the general
187 case. The ``213'' region means |εU|β2|4|¬W|4U|β1|4|¬W|4U|β3,
192 |πif |εU|β1 |πand |εU|β2 |πare chosen at random;
201 the ``321'' region means |εU|β3|4|¬W|4U|β2|4|¬W|4U|β1,
206 |πetc., The probabilities for 123 and 321 are
214 |f1|d34|)|4α_↓|4|ε|≤a/2|4α+↓|4|≤a|g2/2; |πthe
216 probabilities for all other cases are |f1|d38|)|4α+↓|4|ε|≤a/
222 4|4α_↓|4|≤a|g2/4. |πto have all equal to |f1|d36|),
229 we must have |f1|d34|)|4α_↓|4|ε|≤a/2|4α+↓|4|≤a|g2/2|4α=↓|4|f
232 1|d38|)|4α+↓|4|≤a/4|4α_↓|4|≤a|g2/4, |πthat is,
235 |ε1|4α_↓|46|≤a|4α+↓|46|≤a|g2|4α=↓|40. The result
238 of this exercise gives a simple proof of a theorem
248 due to J. Franklin (|εMath. comp. |π|≡1|≡7 (1963),
256 28<59, Theorem 13); other results of that paper
264 are related to exercises 22 and 23.]|'{A6}|≡F|≡i|≡g|≡.|4|4|≡
271 A|≡<|≡3|≡.|9|4Permutation regions for a generator
276 with a potency of 2; |ε|≤a|4α=↓|4(a|4α_↓|41)c/m.|;
282 {A6}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨3|∨.|∨3|∨.|∨4|'
283 {A12}{H9L11}|5|5|≡1|≡.|9|4|ε|≤n|β1 |πis always
286 |εm |πand |ε|≤m|β1|4α=↓|42, |πfor generators
291 of maximum period.|'{A3}|5|5|≡2|≡.|9|4|πLet |εV
296 |πbe the matrix whose rows are |εv|β1,|4.|4.|4.|4,|4v|βt.
303 |πTo minimize |εY|4|¬O|4Y, |πsubject to the condition
310 that |εY|4α=↓|4(0,|4.|4.|4.|4,|40) |πand |εVY
314 |πis an integer column vector |εX, |πis equivalent
322 to minimizing (|εV|gα_↓|g1X)|4|¬O|4(V|gα_↓|g1X),
325 |πsubject to the condition that |εX |πis a nonzero
334 integer column vector. The columns of |εV|gα_↓|g1
341 |πare |εU|β1,|4.|4.|4.|4,|4U|βt.|'{A3}|5|5|≡3|≡.|9|4|εa|g2|4
343 |¬7|42a|4α_↓|41 |πand |εa|g3|4|¬7|43a|4α_↓|42
346 (|πmodulo |εm). |πBy considering all short solutions
353 of (15), we _nd that |ε|≤n|=|β3|g2|4α=↓|46 |πand
360 |ε|≤n|=|β4|g2|4α=↓|44, |πfor the respective vectors
365 (1,|4|→α_↓2,|41) and (1,|4|→α_↓1,|4|→α_↓1,|41),
368 except in the following cases: |εm|4α=↓|42|geq,
374 q |πodd, |εe|4|¬R|43, a|4|¬7|42|ge|gα_↓|g1 (|πmodulo
379 2|ge), |εa|4|¬7|41 (modulo |εq), |≤n|=|β3|g2|4α=↓|4|≤n|=|β4|
383 g2|4α=↓|42; m|4α=↓|43|geq, |πgcd(|ε3,|4q)|4α=↓|41,
386 e|4|¬R|42, a|4|¬7|41|4|¬9|43|ge|gα_↓|g1 (|πmodulo
389 |ε3|ge), a|4|¬7|41 (|πmodulo |εq), |≤n|=|β4|g2|4α=↓|42;
394 m|4α=↓|49, a|4α=↓|44 or 7, |ε|≤n|=|β2|g2|4α=↓|4|≤n|=|β3|g2|4
398 α=↓|45.|'{A3}|5|5|≡4|≡.|9|4(|πa) The unique choice
403 for (|εx|β1,|4x|β2) |πis |ε|f1|d3m|)(y|β1u|β2|β2|4α_↓|4y|β2u
406 |β2|β1, |→α_↓y|β1u|β1|β2|4α+↓|4y|β2u|β1|β1),
408 |πand this is |→|¬7|2|f1|d3|εm|)(y|β1u|β2|β2|4α+↓|4y|β2au|β2
411 |β2, |→α_↓y|β1u|β1|β2|4α_↓|4y|β2au|β1|β2)|4|¬7|4(0,|40)
413 (|πmodulo 1); i.e., |εx|β1 |πand |εx|β2 |πare
420 integers. (b) When (|εx|β1,|4x|β2)|4|=|↔6α=↓|4(0,|40),
424 |πwe have (|εx|β1u|β1|β1|4α+↓|4x|β2u|β2|β1)|g2|4α+↓|4(x|β1u|
426 β1|β2|4α+↓|4x|β2u|β2|β2)|g2|4α=↓|4x|=|β1|g2(u|=|β1|g2|β1|4α+
426 ↓|4u|=|β1|g2|β2)|4α+↓|4x|=|β2|g2(u|=|β2|g2|β1|4α+↓|4|=|β2|g2
426 |β2)|4α+↓|42x|β1x|β2(u|β1|β1u|β2|β1|4α+↓|4u|β1|β2u|β2|β2)|4|
426 ¬R|4(x|=|β1|g2|4α+↓|4x|=|β2|g2|4α_↓|4|¬Gx|β1x|β2|¬G)(u|=|β1|
426 g2|β1|4α+↓|4u|=|β1|g2|β2)|4|¬R|4u|=|β1|g2|β1|4α+↓|4u|=|β1|g2
426 |β2. [|πNote that this si a stronger result than
435 Lemma A, which tells us only that |εx|=|β1|g2|4|¬E|4(u|=|β1|
442 g2|β1|4α+↓|4u|=|β1|g2|β2)(u|=|β2|g2|β1|4α+↓|4u|=|β2|g2|β2)/m
442 |g2, x|=|β2|g2|4|¬E|4(u|=|β1|g2|β1|4α+↓|4u|=|β1|g2|β2)|g2/m|
443 g2, |πand the latter can be |→|¬R1. The idea
452 is essentially Gauss's notion of a reduced binary
460 quadratic form, |εDisq. Arith. (Leipzig, 1801),
466 |πSection 171.]|'{A3}|5|5|≡5|≡.|9|4Conditions
469 (30) remain invariant; hence |εh |πcannot be
476 zero in step S2, when |εa |πis relatively prime
485 to |εm. |πSince |εh |πalways decreases in that
493 step, S2 eventually terminates with |εu|g2|4α+↓|4v|g2|4|¬R|4
498 s. |πNote that |εpp|¬S|4|¬E|40 |πthroughout the
504 calculation.|'!|9|7The hinted inequality surely
509 holds the _rst time step S2 is done. The integer
519 |εq|¬S |πwhich minimizes (|εh|¬S|4α_↓|4qh)|g2|4α+↓|4(p|¬S|4α
522 _↓|4q|¬Sp)|g2 |πis |εq|¬S|4α=↓|4|πround{H11}({H9}h|¬Sh|4α+↓|
524 4|εp|¬Sp)/(h|g2|4α+↓|4p|g2){H12}){H9L11}), |πby
526 (24). If (|εh|¬S|4α_↓|4q|¬Sh)|g2|4α+↓|4(p|¬S|4α_↓|4q|¬Sp)|g2
528 |4|¬W|4h|g2|4α+↓|4p|g2 |πwe must have |εq|¬S|4|=|↔6α=↓|40,
533 q|¬S|4|=|↔6α=↓|4|→α_↓1, |πhence (|εp|¬S|4α_↓|4q|¬Sp)|g2|4|¬R
535 |4p|g2, |πhence (|εh|¬S|4α_↓|4q|¬Sh)|g2|4|¬W|4h|g2,
538 |πi.e., |¬G|εh|¬S|4α_↓|4q|¬Sh|¬G|4|¬W|4h, |πi.e.
541 |εq|¬S|4α=↓|4q |πor |εq|4α+↓|41. |πWe have |εhu|4α+↓|4pv|4|¬
546 R|4h(h|¬S|4α_↓|4q|¬Sh)|4α+↓|4p(p|¬S|4α_↓|4q|¬Sp)|4|¬R|4|→α_↓
546 |f1|d32|)(h|g2|4α+↓|4p|g2), |πso if |εu|g2|4α+↓|4v|g2|4|¬W|4
549 s |πthe next iteration of step S2 will preserve
558 the assumption in the hint. If |εu|g2|4α+↓|4v|g2|4|¬R|4s|4|¬
564 Q|4(u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2, |πwe
566 have 2|¬G|εh(u|4α_↓|4h)|4α+↓|4p(v|4α_↓|4p)|¬G|4α=↓|42{H11}){
567 H9}h(h|4α_↓|4u)|4α+↓|4p(p|4α_↓|4v){H12}){H9}α=↓|4(|εu|4α_↓|4
567 h)|g2|4α+↓|4(v|4α_↓|4p)|g2|4α+↓|4h|g2|4α+↓|4p|g2|4α_↓|4(u|g2
567 |4α+↓|4v|g2)|4|¬E|4(u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2|4|¬E|
567 4h|g2|4α+↓|4p|g2, |πhence (|εu|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)
569 |g2 |πis minimal by exercise 4. Finally if both
578 |εu|g2|4α+↓|4v|g2 |πand (|εu|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g
580 2 |πare |→|¬R|εs, |πlet |εu|¬S|4α=↓|4h|¬S|4α_↓|4q|¬Sh,
585 v|¬S|4α=↓|4p|¬S|4α_↓|4q|¬Sp; |πthen 2|¬G|εhu|¬S|4α+↓|4pv|¬S|
587 ¬G|4|¬E|4h|g2|4α+↓|4p|g2|4|¬E|4u|¬S|g2|4α+↓|4v|¬S|g2,
588 |πand |εh|g2|4α+↓|4p|g2 |πis minimal by exercise
594 4.|'{A3}|5|5|≡6|≡.|9|4|πIf |εu|g2|4α+↓|4v|g2|4|¬R|4s|4|¬Q|4(
596 u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2 |πin the previous
600 answer, we have (|εv|4α_↓|4p)|g2|4|¬Q|4v|g2,
604 |πhence (|εu|4α_↓|4h)|g2|4|¬W|4u|g2; |πand if
608 |εq|4α=↓|4a|βj, |πso that |εh|¬S|4α=↓|4a|βjh|4α+↓|4u,
612 |πwe must have |εa|βj|βα+↓|β1|4α=↓|41. |πIt follows
618 that |ε|≤n|=|β2|g2|4α=↓|4|πmin|ε|β0|β|¬E|βj|β|¬W|βt(m|=|βj|g
619 2|4α+↓|4p|ur2|)jα_↓1|)), |πin the notation of
624 exercise 3.3.3<16.|'!|9|7Now |εm|β0|4α=↓|4m|βjp|βj|4α+↓|4m|β
627 j|βα+↓|β1p|βj|βα_↓|β1|4α=↓|4a|βjm|βjp|βj|βα_↓|β1|4α+↓|4m|βjp
627 |βj|βα_↓|β2|4α+↓|4m|βj|βα+↓|β1p|βj|βα_↓|β1|4|¬W|4(a|βj|4α+↓|
627 41|4α+↓|41/a|βj)m|βjp|βj|βα_↓|β1|4|¬E|4(A|4α+↓|41|4α+↓|41/A)
627 m|βjp|βj|βα_↓|β1, |πand |εm|=|βj|g2|4α+↓|4p|ur2|)jα_↓1|)|4|¬
629 R|42m|βjp|βj|βα_↓|β1, |πhence the result.|'{A3}|5|5|≡7|≡.|9|
633 4We shall prove, using condition (19), that |εU|βj|4|¬O|4U|β
640 k|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j |πi= |εV|βj|4|¬O|4V|βk|
645 4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j. |πAssume
650 that |εU|βj|4|¬O|4U|βk|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j,
655 |πand let |εU|βj|4α=↓|4|≤a|β1V|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4
657 |≤a|βtV|βt. |πThen |εU|βj|4|¬O|4U|βk|4α=↓|4|≤a|βk
660 |πfor all |εk, |πhence |εU|βj|4α=↓|4|≤a|βjV|βj,
665 |πand |εV|βj|4|¬O|4V|βk|4α=↓|4|≤a|urα_↓1|)j|)(U|βj|4|¬O|4V|β
666 k)|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j. |πA symmetric
672 argument proves the converse.|'{A3}|5|5|≡8|≡.|9|4Clearly
677 |εv|βt|βα+↓|β1|4|¬E|4|≤n|βt (|πa fact used implicitly
682 in Algorithm S, since |εs |πis not changed when
691 |εt |πincreases). For |εt|4α=↓|42 |πthis is equivalent
698 to (|εm|≤m|β2/|≤p)|g1|g/|g2|4|¬R|4(|f3|d34|)m|≤m|β3/|≤p)|g1|
699 g/|g3, |πi.e., |ε|≤m|β3|4|¬E|4|f4|d33|)|2|¬H|v4m/|≤p|)|4|≤m|
701 ur3/2|)2|). |πThis reduces to |f4|d33|)|310|gα_↓|g4/{H11}|¬H
705 {H10}|v4|ε|≤p|) |πwith the given parameters,
710 but for large |εm |πand _xed |ε|≤m|β2 |πthe{U0}{H10L12M29}W5
folio 690 galley 2
717 8320#Computer Programming|9(Knuth/Addison-Wesley)|9f.
719 690|9Answers|9g. 2a|'{A6}{H9L11M29}|5|5|≡9|≡.|9|4Let
722 |εf|1(y|β1,|4.|4.|4.|4,|4y|βt)|4α=↓|4|≤u; |πthen
724 gcd(|εy|β1,|4.|4.|4.|4,|4y|βt)|4α=↓|41, |πso
726 there is an integer matrix |εW |πof determinant
734 1 having (|εw|β1,|4.|4.|4.|4,|4w|βt) |πas its
739 _rst row. (Prove the latter fact by induction
747 on the magnitude of the smallest nonzero entry
755 in the row.) Now if |εX|4α=↓|4(x|β1,|4.|4.|4.|4,|4x|βt)
761 |πis a row vector, we have |εXW|4α=↓|4X|¬|¬S
768 |πi= |εX|4α=↓|4X|¬SW|gα_↓|g1, |πand |εW|1|gα_↓|g1
772 |πis an integer matrix of determinant 1, hence
780 the form |εg |πde_ned by |εWU |πsatis_es |εg(x|β1,|4.|4.|4.|
787 4,|4x|βt)|4α=↓|4f|1(x|=|β1|¬S,|4.|4.|4.|4,|4x|=|βt|¬S);
788 |πfurthermore |εg(1,|40,|4.|4.|4.|4,|40)|4α=↓|4|≤u.|'
790 !!|2|πWithout loss of generality, assume that
796 |εf|4α=↓|4g. |πIf now |εS |πis any orthogonal
803 matrix, the matrix |εUS |πde_nes the same form
811 as |εU, |πsince (|εXUS)(XUS)|gT|4α=↓|4(XU)(XU)|gT.
815 |πChoosing |εS |πso that its _rst column is a
824 multiple of |εV|β1 |πand its other columns are
832 any suitable vectors, we have|'{A6}|h|πUS|4α=↓|4|7|∂|9|ε|≤a|
837 β1|9|∂|9|≤a|β2|4.|4.|4.|4|≤a|βt|9|∂|E|n|;|>|;
840 |ε|≤a|β1|;|≤a|β2|4.|4.|4.|4|≤a|βt|;>{A4}|>|;0|;
846 >|>|;|¬O|;>|>|πUS|4α=↓|4|7|?|¬O|;|εU|¬S|;>|>|;
858 |¬O|;>|>|;0|;>{A6}|πfor some |ε|≤a|β1,|4|≤a|β2,|4.|4.|4.|4,|
866 4|≤a|βt |πand some (|εt|4α_↓|41)|4α⊗↓|4(t|4α_↓|41)
870 |πmatrix |εU|¬S. |πHence |εf|1(x|β1,|4.|4.|4.|4,|4x|βt)|4α=↓
873 |4(|≤a|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤a|βtx|βt)|g2|4α+↓|
873 4h(x|β2,|4.|4.|4.|4,|4x|βt). |πIt follows that
877 |ε|≤x|β1|4α=↓|4{H11}|¬H{H9}|v4|≤u|) [|πin fact,
880 |ε|≤x|βj|4α=↓|4(U|β1|4|¬O|4U|βj)/{H11}|¬H{H9}|v4|≤u|)
881 |πfor |ε1|4|¬E|4j|4|¬E|4t], |πand that |εh |πis
887 a positive de_nite quadratic form de_ned by |εU|¬S,
895 |πwhere det |εU|¬S|4α=↓|4(|πdet|4|εU)/{H11}|¬H{H9}|v4|≤u|).
898 |πBy induction on |εt, |πthere are integers (|εx|β2,|4.|4.|4
905 .|4,|4x|βt) |πwith |εh(x|β2,|4.|4.|4.|4,|4x|βt)|4|¬E|4(|f4|d
907 33|))|g(|gt|gα_↓|g2|g)|g/|g2|2|¬G|πdet|4|εU|¬G|g2|g/|g(|gt|g
907 α_↓|g1|g)/|≤u|g1|g/|g(|gt|gα_↓|g1|g), |πand for
910 these integer values we can choose |εx|β1 |πso
918 that |¬G|εx|β1|4α+↓|4(|≤a|β2x|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|
919 ≤a|βtx|βt)/|≤a|β1|¬G|4|¬E|4|f1|d32|), |πi.e.,
921 (|ε|≤a|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤a|βtx|βt)|g2|4|¬E|
921 4|f1|d34|)|≤u. |πHence |ε|≤u|4|¬E|4|εf|1(x|β1,|4.|4.|4.|4,|4
923 x|βt)|4|¬E|4|f1|d34|)|≤u|4α+↓|4(|f4|d33|))|g(|gt|gα_↓|g2|g)|
923 g/|g2|2|¬G|πdet|4|εU|¬G|g2|g/|g(|gt|gα_↓|g1|g)/|≤u|g1|g/|g(|
923 gt|gα_↓|g1|g) |πand the desired inequality follows
929 immediately.|'!!|2[For |εt|4α=↓|42 |πthe result
934 is best possible. For general |εt, |πHermite's
941 theorem implies that |ε|≤m|βt|4|¬E|4|≤p|gt|g/|g2(4/3)|gt|g(|
944 gt|gα_↓|g1|g)|g/|g4/(t/2)*3. |πA fundamental theorem
948 due to Minkowski (``Every |εt-|πdimensional convex
954 set symmetric about the origin with volume |ε|→|¬R2|gt
962 |πcontains a nonzero integer point'') gives |ε|≤m|βt|4|¬E|42
968 |gt; |πthis is stronger than Hermite's theorem
975 for |εt|4|¬R|49. |πAnd even stronger results
981 are known, cf. (41).]|'{A3}|≡1|≡0|≡.|9|4|πSince
986 |εy|β1 |πand |εy|β2 |πare relatively prime, we
993 can solve |εu|β1y|β2|4α_↓|4u|β2y|β1|4α=↓|4m;
996 |πfurthermore (|εu|β1|4α+↓|4qy|β1)y|β2|4α_↓|4(u|β2|4α+↓|4qy|
997 β2)y|β1|4α=↓|4m |πfor all |εq, |πso we can ensure
1005 that 2|¬G|εu|β1y|β1|4α+↓|4u|β2y|β2|¬G|4|¬E|4y|=|β1|g2|4α+↓|4
1006 y|=|β2|g2 |πby choosing an appropriate integer
1012 |εq. |πNow |εy|β2(u|β1|4α+↓|4au|β2)|4|"o|4y|β2u|β1|4α_↓|4y|β
1014 1u|β2|4|"o|40 (|πmodulo |εm), |πand |εy|β2 |πmust
1020 be relatively prime to |εm, |πhence |εu|β1|4α+↓|4au|β2|4|"o|
1026 40. |πFinally let |¬G|εu|β1y|β1|4α+↓|4u|β2y|β2|¬G|4α=↓|4|≤am
1029 , u|=|β1|g2|4α+↓|4u|=|β2|g2|4α=↓|4|≤bm, y|=|β1|g2|4α+↓|4y|=|
1031 β2|g2|4α=↓|4|≤gm; |πwe have |ε0|4|¬E|4|≤a|4|¬E|4|f1|d32|)|≤g
1034 . |πand it remains to be shown that |ε|≤a|4|¬E|4|f1|d32|)|≤b
1042 |πand |ε|≤b|≤G|4|¬R|41. |πThe identity (|εu|β1y|β2|4α_↓|4u|
1047 β2y|β1)|g2|4α+↓|4(u|β1y|β1|4α+↓|4u|β2y|β2)|g2|4α=↓|4(u|=|β1|
1047 g2|4α+↓|4u|=|β2|g2)(y|=|β1|g2|4α+↓|4y|=|β2|g2)
1048 |πimplies that 1|4α+↓|4|≤a|g2|4α=↓|4|≤b|≤g. |πIf
1052 |ε|≤a|4|¬Q|4|f1|d32|)|≤b, |πwe have |ε2|≤a|≤g|4|¬Q|41|4α+↓|4
1055 |≤a|g2, |πi.e., |ε|≤g|4α_↓|4{H11}|¬H{H9}|v4|≤g|g2|4α_↓|41|)|
1057 4|¬W|4|≤a|4|¬E|4|f1|d32|)|≤g. |πBut |f1|d32|)|ε|≤g|4|¬W|4{H1
1059 1}|¬H{H9}|v4|≤g|g2|4α_↓|41|) |πimplies that |ε|≤g|g2|4|¬Q|4|
1062 f4|d33|), |πa contradiction.|'{A3}|≡1|≡1|≡.|9|πSince
1066 |εa |πis odd, |εy|β1|4α+↓|4y|β2 |πmust be even.
1073 To avoid solutions with |εy|β1 |πand |εy|β2 |πboth
1081 even, let |εy|β1|4α=↓|4x|β1|4α+↓|4x|β2, y|β2|4α=↓|4x|β1|4α_↓
1084 |4x|β2, |πand solve |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α=↓|4|εm/{H
1087 11}|¬H{H9}|v43|)|4α_↓|4|≤e, |πwith (|εx|β1,|4x|β2)
1090 |πrelatively prime and |εx|β1 |πeven; |πthe corresponding
1097 multiplier |εa |πwill be the solution to (|εx|β2|4α_↓|4x|β1)
1104 a|4|"o|4x|β2|4α+↓|4x|β1 (|πmodulo 2|ε|ge). |πIt
1108 is not di∃cult to prove that |εa|4|"o|41 (|πmodulo
1116 2|ε|gk|gα+↓|g1) |πi= |εx|β1|4|"o|40 (|πmodulo
1120 |ε2|gk), |πso we get the best potency when |εx|β1
1129 |πmod 4|4α=↓|42. The problem reduces to _nding
1136 relatively prime solutions to |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α
1140 =↓|4N |πwhere |εN |πis a large integer of the
1149 form |ε4k|4α+↓|41. |πBy factoring |εN |πover
1155 the Gaussian integers, we can see that solutions
1163 exist if and only if each prime factor of |εN
1173 (|πover the usual integers) has the form |ε\**k*?*?an
1181 integers, we can see that solutions exist if
1189 and only if each prime factor of |εN (|πover
1198 the usual integers) has the form |ε4k|4α+↓|41.|'
1205 !!|2|πAccording to a famous theorem of Fermat,
1212 every prime |εp |πof the form |ε4k|4α+↓|41 |πcan
1220 be written |εp|4α=↓|4u|g2|4α+↓|4v|g2|4α=↓|4(u|4α+↓|4iv)(u|4α
1222 _↓|4iv), v |πeven, in a unique way except for
1231 the signs of |εu |πand |εv. |πThe numbers |εu
1240 |πand |εv |πcan be calculated e∃ciently by solving
1248 |εx|g2|4|"o|4|→α_↓1 (|πmodulo |εp), |πthen calculating
1253 |εu|4α+↓|4iv|4α=↓|4|πgcd(|εx|4α+↓|4i,|4p) |πby
1255 Euclid's algorithm over the Gaussian integers.
1261 [We can take |εx|4α=↓|4n|g(|gp|gα_↓|g1|g)|g/|g4
1265 |πmod|6|εp |πfor almost half of all integers
1272 |εn. |πThis application of a Euclidean algorithm
1279 is essentially the same as _nding the least nonzero
1288 |εu|g2|4α+↓|4v|g2 |πsuch that |εu|4|¬N|4xv|4|"o|40
1292 (|πmodulo |εp)*3] |πIf the prime factorization
1298 of |εN |πis |εp|ure|β1|)1|)|4.|4.|4.|4p|ure|βr|)r|)|4α=↓|4(u
1301 |β1|4α+↓|4iv|β1)|ge|r1 (u|β1|4α_↓|4iv|β1)|ge|r1|4.|4.|4.|4(u
1302 |βr|4α+↓|4iv|βr)|ge|rr(u|βr|4α_↓|4iv|βr)|ge|rr,
1303 |πwe get |ε2|gr|gα_↓|g1 |πdistinct solutions
1308 to |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α=↓|4N, |πgcd(|εx|β1,|4x|β2)
1310 |4α=↓|41, x|β1 |πeven, by letting |ε|¬Gx|β2|¬G|4α+↓|4i|¬Gx|β
1315 1|¬G|4α=↓|4(u|β1|4α+↓|4iv|β1)|ge|r1(u|β2|4|¬N|4iv|β2)|ge|r2|
1315 4.|4.|4. (u|βr|4|¬N|4iv|βr)|ge|rr; |πand all
1319 such solutions are obtained in this way.|'!!|2|εNote|*/:
1327 |\|εWhen |εm|4α=↓|410|ge, |πa similar procedure
1332 can be used, but it's _ve times as much work
1342 since we must keep trying until _nding a solution
1351 with |εx|β1|4|"o|40 (|πmodulo 10). For example,
1357 when |εm|4α=↓|410|g1|g0 |πwe have |"l|εm/{H11}|¬H{H9}|v43|)|
1361 ¬L|4α=↓|4|π5773502691, and 5773502689|4α=↓|453|4|¬O|41089340
1363 13|4α=↓|4(7|4α+↓|42|εi)(7|4α_↓|42i)(2203|4α+↓|410202i)(2203|
1363 4α_↓|410202i). |πOf the two solutions |¬G|εx|β2|¬G|4α+↓|4i|¬
1368 Gx|β1|¬G|4α=↓|4(7|4α+↓|42i)(2203|4α+↓|410202i)
1369 |πor (|ε7|4α+↓|42i)(2203|4α_↓|410202i), |πthe
1372 former gives |¬G|εx|β1|¬G|4α=↓|467008 (no good)
1377 and the latter gives |¬Gx|β1|¬G|4α=↓|475820,
1382 |¬G|εx|β2|¬G|4α=↓|4|π4983 (which is usable).
1386 Line 9 of Table |π1 was obtained by taking |εx|β1|4α=↓|47582
1395 0, |εx|β2|4α=↓|4|→α_↓4983.|'!!|2|πLine 20 of
1400 the table was obtained as follows: |"l2|g3|g5/{H11}|¬H{H9}|v
1406 43|)|¬L|4α=↓|419837604196; 19837604193 is divisible
1410 by 3 so it is ineligible; 19837604189 is divisible
1419 by 19, and 19837604185 by 7, and 19837604181
1427 by 3; 19837604177 is prime and equals 131884|g2|4α+↓|449439|
1434 g2. The corresponding multiplier is 1175245817;
1440 a better one could be found if we continued searching.
1450 The multiplier on line 24 was obtained as the
1459 be{U0}{H9L11M29}W58320#Computer Programming|9(Knuth/Addison-
folio 693 galley 3
1460 Wesley)|9f. 693|9Answers|9g. 3a|'{A6}|≡1|≡2|≡.|9|4|εU|=|βj|g
1463 |¬S|4|¬O|4U|=|βj|g|¬Sα=↓U|βj|4|¬O|4|βjα+↓2|¬K|βi|βα=↓|βjq|βi
1463 U|βi|4|¬O|4U|βj|4α+↓|4|¬K|βi|βα=↓|βj|¬K|βk|βα=↓|βjq|βiq|βkU|
1463 βi|4|¬O|4U|βk. |πThe partial derivative with
1468 respect to |εq|βk |πis twice the left-hand side
1476 of (26). If the minimum can be achieved, these
1485 partial derivatives must all vanish.|'{A3}|≡1|≡3|≡.|9|4|εu|β
1490 1|β1|4α=↓|41, u|β2|β1|4α=↓|4|πirrational, |εu|β1|β2|4α=↓|40.
1492 |'{A3}|π|≡1|≡4|≡.|9|4After three uclidean steps
1497 we _nd |ε|≤n|=|β2|g2|4α=↓|45|g2|4α+↓|45|g2, |πthen
1501 S4 produces|'{A6}|εU|4α=↓|4|≥a|(|5|5|→α_↓5!|9|75!|9|7|d5|(|→
1503 α_↓18!|→α_↓2!|9|70|q|d5!|4|41!|→α_↓2!|9|71|)|)|≥s,!!V|4α=↓|4
1503 |≥a|(|→α_↓2!|618!|5|5|d5|(|→α_↓5!|→α_↓5!|4|→α_↓5|q|d5|9|70!|
1503 9|70!100|)|)|≥s.|;{A6}|πTransformations (|εj,|4q|β1,|4q|β2,|
1505 4q|β3)|4α=↓|4(1,|4|≤⊂,|40,|42), (2,|4|→α_↓4,|4|≤⊂,|41),
1507 (3,|40,|40,|4|≤⊂), (1,|4|≤⊂,|40,|40) |πresult
1510 in|'{A6}|εU|4α=↓|4|≥a|(|→α_↓3!|9|71!|9|72|d5|(|→α_↓5!|→α_↓8!
1511 |→α_↓7|q|d5|9|71!|→α_↓2!|9|71|)|)|≥s,!!V|4α=↓|4|≥a|(|→α_↓22!
1511 |5|5|→α_↓2!|618|d5|(|5|5|→α_↓5!|5|5|→α_↓5!|→α_↓5|q|d5!|4|49!
1511 |→α_↓31!|629|)|)|≥s,!!Z|4α=↓|4(0!0!1).|;{A6}|πThus
1513 |ε|≤n|β3|4α=↓|4{H10}|¬H{H9}|v46|), |πas we already
1517 knew from exercise 3.|'{A3}|≡1|≡5|≡.|9|4The largest
1523 achievable |εq |πin (11), minus the smallest
1530 achievable, plus 1, is |¬G|εu|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓
1534 |4|¬Gu|βt|¬G|4α_↓|4|≤d, |πwhere |ε|≤d|4α=↓|41
1537 |πif |εu|βiu|βj|4|¬WQ|4*?*?*?vable, plus 1, is |¬G|εu|β1|¬G|4α+
1542 ↓|4|¬O|4|¬O|4|¬O|4α+↓|4|¬Gu|βt|¬G|4α_↓|4|≤d,
1543 |πwhere |ε|≤d|4α=↓|41 |πif |εu|βiu|βj|4|¬W|40
1547 |πfor some |εi |πand |εj, |πotherwise |ε|≤d|4α=↓|40.
1554 |πFor example if |εt|4α=↓|45, u|β1|4|¬Q|40, u|β3|4|¬Q|40,
1560 u|β4|4α=↓|40, |πand |εu|β5|4|¬W|40, |πthe largest
1565 achievable value is |εq|4α=↓|4u|β1|4α+↓|4u|β2|4α+↓|4u|β3|4α_
1568 ↓|41 |πand the smallest achievable is |εq|4α=↓|4u|β5|4α+↓|41
1574 |4α=↓|4|→α_↓|¬Gu|β5|¬G|4α+↓|41.|'!|9[|πNote that
1577 the number of hyperplanes is unchanged when |εc
1585 |πvaries, hence the same answer applies to the
1593 problem of covering |εL |πinstead of |εL|β0.
1600 |πHowever, the stated formula is |εnot |πalways
1607 exact for covering |εL|β0, |πsince the hyperplanes
1614 which intersect the unit hypercube may not all
1622 contain points of |εL|β0. |πFor example, we can
1630 never achieve the value |εq|4α=↓|4u|β1|4α+↓|4u|β2|4α+↓|4u|β3
1634 |4α_↓|41 |πin |εL|β0 |πif |εu|β1|4α+↓|4u|β2|4α+↓|4u|β3|4|¬Q|
1638 4m; |πit is achievable i= there is a solution
1647 to |εm|4α_↓I4*?*?it is achievable i= there is a
1655 solution to |εm|4α_↓|4u|β1|4α_↓|4u|β2|4α_↓|4u|β3|4α=↓|4x|β1u
1657 |β1|4α+↓|4x|β2u|β2|4α+↓|4x|β3u|β3|4α+↓|4x|β4|¬Gu|β5|¬G
1658 |πin nonnegative integers (|εx|β1,|4x|β2,|4x|β3,|4x|β4).
1662 |πIt may be true that the stated limits are always
1672 achievable when |¬Gu|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|¬Gu|βt|¬
1674 G |πis minimal, but this does not appear to be
1684 obvious.]|'{A3}|≡1|≡6|≡.|9|4It su∃ces to determine
1689 all solutions to (15) having minimum |¬G|εu|β1|¬G|4α+↓|4|¬O|
1695 4|¬O|4|¬O|4α~∩↓4|¬Gu|βt|¬G, |πsubtracting 1 if
1699 any one of these solutions has components of
1707 opposite sign.|'!|9Instead of posuppi*?*?*?*?ng 1
1713 if any one of these solutions has components
1721 of opposite sign.|'!|9Instead of positive de_nite
1728 quadratic forms, we work with |εf|1(x|β1,|4.|4.|4.|4,|4x|βt)
1733 |4α=↓|4|¬Gx|β1U|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4x|βtU|βt|¬G,
1734 |πde_ning |¬G|εY|¬G|4α=↓|4|¬Gy|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+
1735 ↓|4|¬Gy|βt|¬G. |πInequality (21) can be replaced
1741 by |¬G|εx|βk|¬G|4|¬E|4(|πmax|ε|β1|β|¬E|βj|β|¬E|βt|2|¬Gv|βk|β
1742 j|¬G)|1f|1(y|β1,|4.|4.|4.|4,|4y|βt).|'!|9|πThus
1744 a workable algorithm can be obtained as follows.
1752 Replace steps S1 through S3 by: ``Set |εU|5|¬L|5(m),
1760 V|5|¬L|5(1), r|5|¬L|51, s|5|¬L|5m, t|5|¬L|51.''
1764 (Here |εU |πand |εV |πare 1|4α⊗↓|41 matrices;
1771 thus the two-dimensional case will be handled
1778 by the general method. A special procedure for
1786 |εt|4α=↓|42 |πcould, of course, be devised.)
1792 In steps S4 and S8, set |εs|5|¬L|5|πmin(|εs,|4|¬GU|βk|¬G),
1799 |πIn step S8, set |εz|βk|5|¬L|5|"l|πmax|ε|β1|β|¬E|βj|β|¬E|βt
1803 |¬Gv|βk|βj|¬Gs/m|¬L. |πIn step S10, set |εs|5|¬L|5|πmin(|εs,
1808 |4|¬GY|¬G|4α_↓|4|≤d); |πand in step S11, output
1814 |εs|4α=↓|4N|βt. |πOtherwise leave the algorithm
1819 as it stands, since it already produces suitably
1827 short vectors. [|εMath. Comp. |π|≡2|≡9 (1975),
1833 827<833.]|'{A3}|≡1|≡7|≡.|9|4When |εk|4|¬Q|4t
1836 |πin S10, and if |εY|4|¬O|4Y|4|¬E|4s, |πoutput
1842 |εY (|πand also |ε|→α_↓Y, |πif desired for completeness);
1850 if |εY|4|¬O|4Y|4|¬W|4s, |πtake back the previous
1856 output of vectors for this |εt. [|πIn the author's
1865 experience preparing Table 1, there was exactly
1872 one vekctttt |εY|4|¬O|4Y|4|¬E|4s, |πoutput |εY
1877 (|πand also |ε|→α_↓Y, |πif desired for completeness);
1884 if |εY|4|¬O|4Y|4|¬W|4s, |πtake back the previous
1890 output of vectors for this |εt. [|πIn the author's
1899 experience preparing Table 1, there was exactly
1906 one vector output for each |ε|≤n|βt, |πexcept
1913 when |εy|β1|4α=↓|40 |πor |εy|βt|4α=↓|40.]|'|≡1|≡8|≡.|9|4a)
1918 |πLet |εx|4α=↓|4m, y|4α=↓|4(1|4α_↓|4m)/3, v|βi|βj|4α=↓|4y|4α
1921 +↓|4x|≤d|βi|βj, u|βi|βj|4α=↓|4|→α_↓y|4α+↓|4|≤d|βi|βj.
1923 |πThen |εV|βj|4|¬O|4V|βk|4α=↓|4|f1|d33|)(m|g2|4α_↓|41)
1925 |πfor |εj|4|=|↔6α=↓|4k, |εV|βk|4|¬O|4V|βk|4α=↓|4|f2|d33|)(m|
1927 g2|4α+↓|4|f1|d32|)), U|βj|4|¬O|4U|βj|4α=↓|4|f1|d33|)(m|g2|4α
1928 +↓|42), |εz|βk|4|¬x|4{H10}|¬H{H9}|v4|f2|d39|)|)|4m.
1930 (|πThis example satis_es (28) with |εa|4α=↓|41
1936 and works for all |εm|4|≠-|41 (|πmodulo 3).)|'
1943 !!|2|πb) Interchange the roll!!|2|πb) Interchange
1948 the roles of |εU |πand |εV |πin step S5. Also
1958 set |εs|5|¬L|5|πmin(|εs,|4U|βi|4|¬O|4U|βi) |πfor
1961 all |εU|βi |πthat change. For example, when |εm|4α=↓|464
1969 |πthis transformation with |εj|4α=↓|41, |πapplied
1974 to the matrices of (a), reduces|'{A9}{M36}|εV|4α=↓|4|≥a|(|9|
1980 743!|→α_↓21!|→α_↓21|d5|(|→α_↓21!!|9|743!|→α_↓21|q|d5|→α_↓21!
1980 |→α_↓21!|9|7|)|)|≥s,!U|4α=↓|4|≥a|(22!21!21|d5|(21!22!21|q|d5
1980 21!21!22|)|)|≥s!!|πto!!|εV|4α=↓|4|≥a|(!|4|41!!|4|41!!|4|41|d
1980 5|(|→α_↓21!|9|743!|→α_↓21|q|d5|→α_↓21!|→α_↓21!|9|743|)|)|≥s,
1980 !U|4α=↓|4|≥a|(|622!21!21|d5|(|→α_↓1!|5|51!|5|5|q|d5|→α_↓1!|5
1980 |50!|5|51|)|)|≥s.|'{A9}{M29}[|πSince the transformation
1984 can increase the length of |εV|βj, |πan algorithm
1992 which incorporates both transformations must
1997 be careful to avoid in_nite looping.]|'{A3}|≡1|≡9|≡.|9|4No,
2004 since a product of non-identity matrices with
2011 all o=-diagonal elements nonnegative and all
2017 diagonal elements 1 cannot be the identity. [However,
2025 looping would be possible if a subsequent transformation
2033 with |εq|4α=↓|4|→α_↓1 |πwere performed when |ε|→α_↓2V|βi|4|¬
2038 O|4V|βj|4α=↓|4V|βj|4|¬O|4V|βj; |πthe rounding
2041 rule must be asymmetric with respect to sign
2049 if non-shortening transformations are allowed.]|'
2054 {A3}|≡2|≡0|≡.|9|4Use the ordinary spectral test
2059 for |εa |πand |εm|4α=↓|42|ge|gα_↓|g2; |πvkf.*?*?pect
2064 to sign if non-shortening transformations are
2070 allowed.]|'{A3}|≡2|≡0|≡.|9|4Use the ordinary
2074 spectral test for |εa |πand |εm|4α=↓|42|ge|gα_↓|g2;
2080 |πcf. exercise 3.2.1.2<9. [On intuitive grounds,
2086 the same answer should apply also when |εa |πmod
2095 8|4α=↓|43.]|'{A3}|≡2|≡1|≡.|9|4|εX|β4|βn|βα+↓|β4|4|≠-|4X|β4|β
2096 n (|πmodulo 4), so it is appropriate to let |εV|β1|4α=↓|4(4,
2105 |44a|g2,|44a|g3)/m, |εV|β2|4α=↓|4(0,|41,|40),
2107 V|β3|4α=↓|4(0,|40,|41) de_ne the corresponding
2111 lattice |εL|β0.|'{A3}|≡2|≡4|≡.|9|4|πLet |εm|4α=↓|4p;
2115 |πan analysis paralleling the text can be given.
2123 For example, when |εt|4α=↓|44 |πwe have |εX|βn|βα+↓|β3|4α=↓|
2129 4{H11}({H9}(a|g2|4α+↓|4b)X|βn|βα+↓|β1|4α+↓|4abX|βn{H11}){H9}
2129 |πmod|4|εn, |πand we want to minimize |εu|=|β1|g2|4α+↓|4u|=|
2135 β2|g2|4α+↓|4u|=|β3|g2|4α+↓|4u|=|β4|g2|4|=|↔6α=↓|40
2136 |πsuch that |εu|β1|4α+↓|4bu|β3|4α+↓|4abu|β4|"o|4u|β2|4α+↓|4a
2138 u|β3|4α+↓|4(a|g2|4α+↓|4b)u|β4|4|"o|40 (|πmodulo
2140 |εm).|'!|9|πReplace steps S1 through S3 by the
2148 operations of setting|'{A6}|εU|4|"L|5|↔a|(m|d50|)!|(0|d5m|)|
2151 ↔s,!!V|5|¬L|5|↔a|(1!0|d50!1|)|↔s,!!R|5|¬L|5|↔a|(1!0|d50!1|)|
2151 ↔s,!!s|5|¬L|5m|g2,!!t|5|¬L|52,|;{A9}|πand outputting
2154 |ε|≤n|β2|4α=↓|4m. |πReplace step S4 by|'{A3}{I1.7L}{I1.7H}|π
2159 |≡S|≡4|¬S|≡.|9[Advance |εt.] |πIf |εt|4α=↓|4T,
2163 |πthe algorithm terminates. Otherwise set |εt|5|¬L|5t|4α+↓|4
2168 1 |πand |εR|5|¬L|5R(|f0|d51|)!|fb|d5a|))|πmod|4|εm.
2171 |πSet |εU|βt |πto the new row (|→α_↓|εr|β1|β2,|4|→α_↓r|β2|β2
2177 ,|40,|4.|4.|4.|4,|40,|41) |πof |εt |πelements,
2181 and set |εu|βi|βt|5|¬L|50 |πfor |ε1|4|¬E|4i|4|¬W|4t.
2186 |πSet |εV|βt |πto the new row (0,|4.|4.|4.|4,|40,|4|εm).
2193 |πFor |ε1|4|¬E|4|εi|4|¬W|4t, |πset |εq|5|¬L|5|πround{H11}({H
2196 9}(|εv|βi|β1r|β1|β2|4α+↓|4v|βi|β2r|β2|β2)/m{H11}){H9},
2197 v|βi|βt|5|¬L|5v|βi|β1r|β1|β2|4α+↓|4v|βi|β2r|β2|β2|4α_↓|4qm,
2198 |πand |εU|βt|5|¬L|5U|βt|4α+↓|4qU|βi. |πFinally
2201 set |εs|5|¬L|5|πmin(|εs,|4U|βt|4|¬O|4U|βt), k|5|¬L|5t,
2204 j|5|¬L|51.|'!!!!|4[|πA similar generalization
2208 applies to all sequences of length |εp|gk{U0}{H10L12M29}W583
folio 701 galley 4
2214 20#Computer Programming|9(knuth/Addison-Wesley)|9f.
2216 701|9Answers|9g. 4a|'{A6}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|∨3|∨.|∨4|
2218 ∨.|∨1|'{A12}{H9L11}|5|5|≡1|≡.|9|4|ε|≤a|4α+↓|4(|≤b|4α_↓|4|≤a)
2219 U.|'{A3}|5|5|≡2|≡.|9|4|πLet |εU|4α=↓|4X/m; |"lkU|"L|4α=↓|4r
2223 |πif and only if |εr|4|¬E|4kX/m|4|¬W|4r|4α+↓|41,
2228 |πthat is |εmr/k|4|¬E|4X|4|¬W|4m(r|4α+↓|41)/k,
2231 |πthat is |"pmr/k|"P|4|¬E|4X|4|¬W|4|"pm(r|4α+↓|41)/k|"P.
2234 |πThe exact probability is (|ε1/m)(|"pm(r|4α+↓|41)/k|"P|4α_↓
2238 |4|"pmr/k|"P{H11}){H9}|4α=↓|41/k|4α+↓|4|≤e, |¬G|≤e|¬G|4|¬W|4
2239 1/m.|'{A3}|5|5|≡3|≡.|9|4|πIf full-word random
2243 numbers are given, the result will be su∃ciently
2251 random as in exercise 2. But if a linear congruential
2261 sequence is used, |εk |πmust be relatively prime
2269 to the modulus |εm, |πlest the numbers have a
2278 very short period (e.g., if |εk|4α=↓|42 |πand
2285 |εm |πis even, the numbers will at best be alternately
2295 0 and 1), by the results of Section 3.2.1.1.
2304 The method is slower than (1) in nearly every
2313 case, so it is not recommended.|'{A3}|5|5|≡4|≡.|9|4max(|εX|β
2319 1,|4X|β2)|4|¬E|4x |πif and only if |εX|β1|4|¬E|4x
2325 |πand |εX|β2|4|¬E|4x; |πmin(|εX|β1,|4X|β2)|4|¬R|4x
2328 |πif and only if |εX|β1|4|¬R|4x |πand |εX|β2|4|¬R|4x.
2335 |πThe probability that two independent events
2341 both happen is the product of the individual
2349 probabilities.|'|5|5|≡5|≡.|9|4|πObtain independent
2352 uniform deviates |εU|β1, U|β2. |πSet |εX|4|¬L|4U|β2.
2358 |πIf |εU|β1|4|¬R|4p, |πset |εX|4|¬L|4|πmax(|εX,|4U|β3),
2362 |πwhere |εU|β3 |πis a third uniform deviate.
2369 If |εU|β1|4|¬R|4p|4α+↓|4q, |πalso set |εX|5|¬L|5|πmax(|εX,|4
2373 U|β4), |πwhere |εU|β4 |πis a fourth uniform deviate.
2381 This method can obviously be generalized to any
2389 polynomial, and indeed even to in_nite power
2396 series (as shown for example in Algorithm S,
2404 which uses minimization instead of maximization).|'
2410 !!|2Alternatively, we could proceed as follows
2416 (suggested by M. D. MacLaren): If |εU|β1|4|¬W|4p,
2423 |πset |εX|5|¬L|5U|β1/p; |πotherwise if |εU|β1|4|¬W|4p|4α+↓|4
2427 q, |πset |εX|5|¬L|5|πmax{H11}({H9}(|εU|β1|4α_↓|4p)/q,|4U|ε|β
2429 2{H11}){H9}; |πotherwise set |εX|5|¬L|5|πmax{H11}({H9}(|εU|β
2432 1|4α_↓|4p|4α_↓|4q)/r, U|β2,|4U|β3{H11}){H9}.
2434 |π|πThis method requires less time than the other
2442 to obtain the uniform deviates, although it involves
2450 further arithmetical operations and it is less
2457 stable numerically.|'{A6}|5|5|≡6|≡.|9|4|εF(x)|4α=↓|4A|β1/(A|
2459 β1|4α+↓|4A|β2), |πwhere |εA|β1 |πand |εA|β2 |πare
2465 the areas in Fig. A-4; so|'{A6}{M29}|εF(x)|4α=↓|4|(|¬J|urx|)
2471 0|)|4{H10}|¬H{H9}|v21|4α_↓|4y|g2|)|4dy|d2|¬J|ur1|)0|)|4{H10}
2471 |¬H{H9}|v21|4α_↓|4y|g2|)|4dy|)|4α=↓|4|(2|d2|≤p|)|4|πarcsin|4
2471 |εx|4α+↓|4|(2|d2|≤p|)|4x|2{H10}|¬H{H9}|v21|4α_↓|4x|g2|).|'
2472 {A6}|πThe probability of termination at step
2478 2 is |εp|4α=↓|4|≤p/4, |πeach time step 2 is encountered,
2487 so the number of executions of step 2 has the
2497 geometric distribution. The characteristics of
2502 this number are (min|41, ave|44/|ε|≤p, |πmax|4|¬X,
2508 dev|4(|ε4/|≤p)|2{H10}|¬H{H9}|v41|4α_↓|4|≤p/4|)),
2509 |πby exercise 17.|'{A6}|≡F|≡i|≡g|≡.|4|4|≡A|≡<|≡4|≡.|9|4|πReg
2512 ion of ``acceptance'' for the algorithm of exercise
2520 6.|;{A6}|5|5|≡7|≡.|9|4The altitude of |εp|βjf|βj(x)
2525 |πmust not exceed |εf|1(x), |πsince each component
2532 |εf|βk(x) |πof Eq. (14) must be |→|¬R0. Now |εp|βj
2541 |πis the area under the curve |εp|βjf|βj(x),
2548 |πthat is, the altitude of |εp|βjf|βj(x) |πtimes
2555 |f1|d34|). So the given value is the largest
2563 multiple of |f1|d3256|) which satis_es the conditions.{A3}|5
2569 |5|≡8|≡.|9|4The idea is to make the selection
2576 of the large rectangle distributions as e∃cient
2583 as possible. (An analogous situation is given
2590 in exercise 21.)|'{A3}|5|5|≡9|≡.|9|4Consider
2594 the sign of |εf|1|¬P(x)|4α=↓|4{H10}|¬H{H9}|v42/|≤p|)|1(x|g2|
2597 4α_↓|41)e|gα_↓|gx|i2|g/|g2.|'{A3}|≡1|≡0|≡.|9|4|πFigure
2599 10 shows how |εa|βj |πand |εb|βj |πmust be chosen
2608 for the cases that |εf|1(x) |πis concave |πup
2616 or down. Letting |εs|βj|4α=↓|4|f1|d34|)(j|4α_↓|41)
2620 |πand |εh|4α=↓|4|f1|d34|), |πwe _nd that|'{A9}|εf|βj|βα+↓|β2
2625 |β4(x)|4|∂α=↓|4|(1|d2p|βj|βα+↓|β2|β4|)|4|↔H|(2|d2|≤p|)|4(e|g
2625 α_↓|gx|i2|g/|g2|4α_↓|4e|gα_↓|g(|gj|g/|g4|g)|i2|g/|g2),!!s|βj
2625 |4|¬E|4x|4|¬E|4s|βj|4α+↓|4h;|'{A4}| p|βj|βα+↓|β2|β4|4|L|4|↔H
2626 |(2|d2|≤p|)|4|↔j|urs|βjα+↓1/4|)s|βj|)|4(e|gα_↓|gt|i2|g/|g2|4
2626 α_↓|4e|gα_↓|g(|gj|g/|g4|g)|i2|g/|g2)|4dt>{A4}| a|βj|4|L|4f|β
2627 j|βα+↓|β2|β4(s|βj),!!b|βj|4α=↓|4|→α_↓hf|=|βj|¬S|βα+↓|β2|β4(s
2627 |βj|4α+↓|4h),!!|πfor|4|41|4|¬E|4j|4|¬E|44;>{A4}| |εa|βj|4|Lα
2628 =↓|4f|βj|βα+↓|β2|β4(x|βj)|4α+↓|4(x|βj|4α_↓|4s|βj)b|βj/h,!!b|
2628 βj|4α=↓|4f|βj|βα+↓|β2|β4(s|βj),!!|πfor|4|4|ε5|4|¬E|4j|4|¬E|4
2628 12,>{A9}|πwhere |εx|βj |πis the root of the equation
2637 |εf|=|βj|¬S|βα+↓|β2|β4(x|βj)|4α=↓|4|→α_↓b|βj/h.
2638 |πNote that in Eqs. (20) we have |εE[j]|4α=↓|416/j,
2646 |πfor |ε1|4|¬E|4j|4|¬E|44; |εE[j]|4α=↓|41/(e|gj|g/|g1|g6|gα_
2648 ↓|g1|g/|g3|g2|4α_↓|41), |πfor |ε5|4|¬E|4j|4|¬E|412.|'
2651 {A3}|≡1|≡1|≡.|9|4|πLet |εg(t)|4α=↓|4e|g9|g/|g2te|gα_↓|gt|i2|
2652 g/|g2 |πfor |εt|4|¬R|43. |πSince |εG(x)|4α=↓|4|¬J|urx|)0|)|4
2656 g(t)|4dt|4α=↓|41|4α_↓|4e|gα_↓|g(|gx|i2|gα_↓|g9|g)|g/|g2,
2657 |πa random variable |εX |πwith density |εg |πcan
2665 be computed by setting |εX|5|¬L|5G|gα_↓|g1(1|4α_↓|4V)|4α=↓|4
2669 {H10}|¬H{H9}|v49|4α_↓|42|4|πln|4|εV|). |πNow
2671 |εe|gα_↓|gt|i2|g/|g2|4|¬E|4(t/3)e|gα_↓|gt|i2|g/|g2
2672 |πfor |εt|4|¬R|43, |πso we obtain a valid refection
2680 method if we accept |εX |πwith probability |εf|1(X)/cg(X)|4α
2687 =↓|43/X.|'{A3}|≡1|≡2|≡.|9|4|πWe have |εf|¬S(x)|4α=↓|4xf|1(x)
2690 |4α_↓|41|4|¬W|40 |πfor |εx|4|¬R|40, |πsince |εf|1(x)|4α=↓|4x
2694 |gα_↓|g1|4α_↓|4e|gx|i2|g/|g2|3|¬J|ur|¬X|)x|)|3e|gα_↓|gt|i2|g
2694 /|g2|4dt/t|g2 |πfor |εx|4|¬Q|40. |πLet |εx|4α=↓|4a|βj|βα_↓|β
2698 1 |πand |εy|g2|4α=↓|4x|g2|4α+↓|42|4|πln|42; |πthen
2702 {H10}|¬H{H9}|v42/|≤p|)|3|¬J|ur|¬X|)|εy|)|3e|gα_↓|gt|i2|g/|g2
2702 |4dt|4α=↓|4|f1|d32|)|2{H10}|¬H{H9}|v42/|≤p|)|4e|gα_↓|gx|i2|g
2702 /|g2|1f|1(y)|4|¬W|4|f1|d32|)|2{H10}|¬H{H9}|v42/|≤p|)|4e|gα_↓
2702 |gx|i2|g/|g2|1f|1(x)|4α=↓|42|gα_↓|gj, |πhence
2704 |εy|4|¬Q|4a|βj.|'{A3}|≡1|≡3|≡.|9|4take |εb|βj|4α=↓|4|≤m|βj;
2707 |πconsider now the problem with |ε|≤m|βj|4α=↓|40
2713 |πfor each |εj. |πIn matrix notation, if |εY|4α=↓|4AX,
2721 |πwhere |εA|4α=↓|4(a|βi|βj), |πwe need |εAA|gT|4α=↓|4C|4α=↓|
2725 4(c|βi|βj). [|πIn other notation, if |εY|βj|4α=↓|4|¬K|4a|βj|
2730 βkX|βk, |πthen the average value of |εY|βiY|βj
2737 |πis |¬K|4|εa|βi|βka|βj|βk.] |πIf this matrix
2742 equation can be solved for |εA, |πit can be solved
2752 when |εA |πis triangular, since |εA|4α=↓|4BU
2758 |πfor some orthogonal matrix |εU |πand some triangular
2766 |εB, |πand |εBB|gT|4α=↓|4C. |πThe desired triangular
2772 solution can be obtained by solving the equations
2780 |εa|=|β1|g2|β1|4α=↓|4c|β1|β1, a|β1|β1a|β2|β1|4α=↓|4c|β1|β2,
2782 a|=|β2|g2|β1|4α+↓|4a|=|β2|g2|β2|4α=↓|4c|β2|β2,
2783 a|β1|β1a|β3|β1|4α=↓|4c|β1|β3, a|β2|β1a|β3|β1|4α+↓|4a|β2|β2a|
2784 β3|β2|4α=↓|4c|β2|β3,|4.|4.|4.|4,|4 |πsuccessively
2786 for |εa|β1|β1, a|β2|β1, a|β2|β2, a|β3|β1, a|β3|β2,
2792 |πetc. [|εNote|*/: |\|πThe covariance matrix must
2798 be positive semide_ne, since the average value
2805 of (|¬K|4|ε|βy|βjY|βj)|g2 |πis |¬K|4c|βi|βjy|βiy|βj,
2809 |πwhich must be nonnegative. And there is always
2817 a solution when |εC |πis positive semide_nite,
2824 since |εC|4α=↓|4U|gα_↓|g1|4|πdiag(|ε|≤l|β1,|4.|4.|4.|4,|4|≤l
2825 |βn)U, |πwhere the eigenvalues |ε|≤l|βj |πare
2831 nonnegative, and |εU|gα_↓|g1|4|πdiag({H10}|¬H{H9}|v4|ε|≤l|β1
2833 |),|4.|4.|4.|4,|4{H10}|¬H{H9}|v4|≤l|βn|))U |πis
2835 a solution.]|'{A3}|≡1|≡4|≡.|9|4|εF(x/c) |πif
2839 |εc|4|¬Q|40, |πa step function if |εc|4α=↓|40,
2845 |πand |ε1|4α_↓|4F(x/c) |πif |εc|4|¬W|40.|'{A3}|≡1|≡5|≡.|9|4|
2849 πDistribution |¬J|ur|¬X|)α_↓|¬X|)|4|εF|β1(x|4α_↓|4t)|4dF|β2(
2850 t). |πDensity |ε|¬J|ur|¬X|)α_↓|¬X|)|4f|β1(x|4α_↓|4t)|1f|β2(t
2852 )|4dt. |πThis is called the |εconvolution |πof
2859 the given distributions.|'|Ha*?*?{U0}{H9L11M29}W58320#Computer
folio 707 galley 5
2862 Programming|9(Knuth/Addison-Wesley)|9f. 707|9Answers|9g.
2865 5a|'{A6}|≡1|≡6|≡.|9|4|πIt is clear that |εf|1(t)|4|¬E|4cg(t)
2870 |πfor all |εt |πas required. Since |¬J|ur|¬X|)0|)|4g(t)|4dt
2877 |4α=↓|41 |πwe have |εg(t)|4α=↓|4Ct|g9|gα_↓|g1
2881 |πfor |ε0|4|¬E|4t|4|¬W|41, |εCe|gα_↓|gt |πfor
2885 |εt|4|¬R|41, |πwhere |εC|4α=↓|4|εae/(a|4α+↓|4e).
2888 |πA random variable with density |εg |πis easy
2896 to obtain as a mixture of two distributions,
2904 |εG|β1(x)|4α=↓|4x|g1|g/|ga |πfor |ε0|4|¬E|4x|4|¬W|41,
2907 |πand |εG|β2(x)|4α=↓|41|4α_↓|4|εe|g1|gα_↓|gx
2909 |πfor |εx|4|¬R|41:|'{A3}{I3.1H}|π!!|2|≡G|≡1|≡.|9[Initialize.
2911 ] Set |εp|5|¬L|5e/(a|4α+↓|4e). (|πThis is the
2917 probability that |εG|β1 |πshould be used.)|'{A3}!!|2|≡G|≡2|≡
2923 .|9[Generate |εG |πdeviate.] Generate independent
2928 uniform deviates |εU, V, |πwhere |εV|4|=|↔6α=↓|40.
2934 |πIf |εU|4|¬W|4p, |πset |εX|5|¬L|5V|g1|g/|ga
2938 |πand |εq|5|¬L|5e|gα_↓|gX; |πotherwise set |εX|5|¬L|51|4α_↓|
2942 4|πln|4|εV |πand |εq|5|¬L|5X|ga|gα_↓|g1. (|πNow
2946 |εX |πhas density |εg, |πand |εq|4α=↓|4f|1(X)/cg(X).{H11})|'
2952 {A3}{H9}|π!!|2|≡G|≡3|≡.|9[Reject?] Generate a
2955 new uniform deviate |εU. |πIf |εU|4|¬R|4q, |πreturn
2962 to G2.|'{A3}{IC}The average number of iterations
2969 is |ε1/c|4α=↓|4(a|4α+↓|4e)/e|≤)(a|4α+↓|41)|4|¬W|41.4.|'
2971 !|9|πIt is possible to streamline this procedure
2978 in several ways. First, we can replace |εV |πby
2987 an exponential deviate |εY |πof mean 1, generated
2995 by Algorithm S, say, and then we set |εX|5|¬L|5e|gα_↓|gY|g/|
3003 ga |πor |εX|5|¬L|51|5α+↓|5Y |πin the two cases.
3010 Moreover, if we set |εq|5|¬L|5pe|gα_↓|gX |πin
3016 the _rst case and |εq|5|¬L|5|εp|4α+↓|4(1|4α_↓|4p)X|ga|gα_↓|g
3020 1 |πin the second, we can use the original |εU
3030 |πinstead of a newly generated one in step G3.
3039 Finally if |εU|4|¬W|4p/e |πwe can accept |εV|g1|g/|ga
3046 |πimmediately, avoiding the calculation of |εq
3052 |πabout 30 percent of the time.|'{A3}|≡1|≡7|≡.|9|4|π(a)
3059 |εF(x)|4α=↓|41|4α_↓|4(1|4α_↓|4p)|g|¬G|gx|g|¬G,
3060 |πfor |εx|4|¬R|40. |π(b) |εG(z)|4α=↓|4pz/{H11}({H9}1|4α_↓|4(
3063 1|4α_↓|4p)z{H11}){H9}. (c) |πMean |ε1/p, |πstandard
3068 deviation {H10}|¬H{H9}|v41|4|εp/p. |πTo do the
3073 latter calculation, observe that if |εH(z)|4α=↓|4q|4α+↓|4(1|
3078 4α_↓|4q)z, |πthen |εH|¬S(1)|4α=↓|41|4α_↓|4q |πand
3082 |εH|¬C(1)|4α+↓|4H|¬S(1)|4α_↓|4{H11}({H9}H|¬S(1){H11}){H9}|g2
3082 |4α=↓|4q(1|4α_↓|4q), |πso the mean and variance
3088 of |ε1/H(z) |πare |εq|4α_↓|41 |πand |εq(q|4α_↓|41),
3094 |πrespectively. (See Section 1.2.10.) In this
3100 case, |εq|4α=↓|41/p; |πthe extra factor |εz |πin
3107 the numerator of |εG(z) |πincreases the mean
3114 by one.|'|≡1|≡8|≡.|9|4|πSet |εN|5|¬L|5N|β1|4α+↓|4N|β2|4α_↓|4
3117 1, |πwhere |εN|β1 |πand |εN|β2 |πindependently
3123 have the geometric distribution for probability
3129 |εp. (|πConsider the generating function.)|'{A3}|≡1|≡9|≡.|9|
3134 4Set |εN|5|¬L|5N|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4N|βt|4α_↓|4t,
3136 |πwhere the |εN|βj |πhave the geometric distribution
3143 for |εp. (|πThis is the number of failures before
3152 the |εt|πth success, when a sequence of independent
3160 trials are made each of which succeeds with probability
3169 |εp.)|'!!|2|πFor |εt|4α=↓|4p|4α=↓|4|f1|d32|),
3172 |πand in general when the mean value {H11}({H9}|πnamely
3180 |εt(1|4α_↓|4p)/p{H11}) {H9}|πof the distribution
3184 is small, we simply can evaluate the probabilities
3192 |εp|βn |4α=↓|4(|ft|4α_↓|41|4α+↓|4n|d5n|))p|gt(1|4α_↓|4p)|gn
3194 |πconsecutively for |εn|4α=↓|40,|41,|42,|4.|4.|4.
3197 |πas in the following algorithm:|'{A3}{I3.1H}!!|2|≡B|≡1|≡.|9
3202 [Initialize.] Set |εN|5|¬L|50, q|5|¬L|5p|gt,
3206 r|5|¬L|5q, |πand generate a random uniform deviate
3213 |εU. (|πWe will have |εq|4α=↓|4p|βN |πand |εr|4α=↓|4p|β0|4α+
3219 ↓|4|¬O|4|¬O|4|¬O|4α+↓|4p|βN |πduring this algorithm,
3223 which stops as soon as |εU|4|¬W|4r.)|'{A3}!!|2|≡B|≡2|≡.|9[Se
3229 arch.] |πIf |εU|4|¬R|4r, |πset |εN|5|¬L|5N|4α+↓|41,
3234 q|5|¬L|5q(1|4α_↓|4p)(t|4α_↓|41|4α+↓|4N)/N, r|5|¬L|5r|4α+↓|4q
3235 , |πand repeat this step.|'{A3}{IC}!!|2[An interesting
3242 technique for the negative binomial distribution,
3248 for arbitrarily large real values of |εt, |πhas
3256 been suggested by R. L|=1eger: First generate
3263 a random gamma deviate of order |εt, |πthen let
3272 |εN |πbe a random Poisson deviate of mean |εX(1|4α_↓|4p)/p.]
3280 |'{A3}|≡2|≡0|≡.|9|4|πIf |ε0|4|¬E|4|εb|β1b|β2b|β3|4|¬W|46,
3283 |πset |εX|5|¬L|5|εA[b|β1b|β2b|β3]; |πif 48|4|¬E|4|εb|β1b|β2b
3286 |β3b|β4b|β5b|β6|4|¬W|463, |πset |εX|5|¬L|5|εB[b|β1b|β2b|β3b|
3288 β4b|β5b|β6]; |πotherwise set |εX|5|¬L|6|εC[b|β1b|β2b|β3b|β4b
3291 |β5b|β6b|β7b|β8b|β9]. |πHere (|εA[0],|4.|4.|4.|4,|4|εA[5])|4
3293 α=↓|4(x|β1,|4x|β2,|4x|β3,|4x|β3,|4x|β6,|4x|β6);
3294 (|εB[48],|4.|4.|4.|4,|4B[62])|4α=↓|4(|εx|β1,
3295 x|β1, x|β1, x|β2, x|β2, x|β4, x|β5, x|β5, x|β5,
3303 x|β6, x|β6, x|β6, x|β6, x|β6); (C[504],|4.|4.|4.|4,|4C[511])
3308 |4α=↓|4(x|β1, x|β1, x|β2, x|β3, x|β3, x|β3, x|β4,
3315 x|β4).|'!!|2|πThis method uses 29 auxiliary table
3322 entries, which can be overlapped so that only
3330 21 are actually required: Let (|εD[0],|4.|4.|4.|4,|4D[20])|4
3335 α=↓|4(x|β1, x|β1, x|β2, x|β4, x|β5, x|β5, x|β5,
3342 x|β5, x|β6, x|β6, x|β6, x|β6, x|β6, x|β2, x|β1,
3350 x|β3, x|β3, x|β1, x|β3, x|β4, x|β46);*?*?x|β6,
3356 x|β6, x|β6, x|β2, x|β1, x|β3, x|β3, x|β1, x|β3,
3364 x|β4, x|β4); A[j]|4α=↓|4D[j|4α+↓|411], B[j]|4α=↓|4D[j|4α_↓|4
3367 48], C[j]|4α=↓|4D[j|4α_↓|4491].|'{A3}|≡2|≡1|≡.|9|4|πIf
3370 |ε0|4|¬E|4b|β1b|β2b|β3|4|¬W|46, |πset |εX|5|¬L|5A[b|β1b|β2b|
3372 β3]; |πif 48|4|¬E|4|εb|β1b|β2b|β3b|β4b|β5b|β6|4|¬W|463,
3375 |πset |εX|5|¬L|5B[b|β1b|β2b|β3b|β4b|β5b|β6];
3377 |πif 504|4|¬E|4|εb|β1b|β2b|β3b|β4b|β5b|β6b|β7b|β8b|β9];
3379 |πotherwise _nd the smallest |εj |πsuch that
3386 |εU|4|¬W|4P[j], |πand set |εX|5|¬L|5x|βj. |πHere|'
3391 {A9}!!(|εA[0],|4.|4.|4.|4,|4A[5])|4|∂α=↓|4(x|β3,|4x|β6,|4x|β
3391 6,|4x|β1,|4x|β2,|4x|β3);|h|4x|β2,|4x|β2,|4x|β5,|4x|β5,|4x|β5
3391 ,|4x|β6,|4x|β6,|4x|β6,|4x|β6|E|n|'{A11}| (B[48],|4.|4.|4.|4,
3392 |4B[62])|4|Lα=↓|4(|εx|β4,|4x|β5,|4x|β6,|4x|β1,|4x|β1,|4x|β1,
3392 |4x|β2,|4x|β2,|4x|β5,|4x|β5,|4x|β5,|4x|β6,|4x|β6,|4x|β6,|4x|
3392 β6);>| (|εC[504],|4.|4.|4.|4,|4C[509])|4|Lα=↓|4(|εx|β1,|4x|β
3393 3,|4x|β3,|4x|β3,|4x|β4,|4x|β4).>{A9}|πAnd |εP[1]|4α=↓|4|f510
3395 |d3512|)|4α+↓|4|≤e|β1, P[2]|4α=↓|4|f510|d3512|)|4α+↓|4|≤e|β1
3396 |4α+↓|4|≤e|β2,|4.|4.|4.|4,|4P[6]|4α=↓|4|f510|d3512|)|4α+↓|4|
3396 ≤e|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤e|β6|4α=↓|41.
3397 |πThis makes 33 table entries; strictly speaking,
3404 howevjjr,*?*?|4α+↓|4|≤e|β1|4α+↓|4|≤e|β2,|4.|4.|4.|4,|4P[6]|4α=
3404 ↓|4|f510|d3512|)|4α+↓|4|≤e|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤e|
3404 β6|4α=↓|41. |πThis makes 33 table entries; strictly
3411 speaking, however, the elements |εx|βj |πshould
3417 also be considered auxiliary table entries, since
3424 we say ``set |εX|5|¬L|5x|βj'' |πin the algorithm.
3431 The |εx|βj-|πtable appears as the last three
3438 entries of |εA |πand the _rst three entries of
3447 |εB, |πso we arrange to have these tables adjacent
3456 in the computer memory. Further overlap is also
3464 possible, as in exercise 20. Note that the technique
3473 considered in this exercise is essentially the
3480 ``rectangle'' part of the rectangle-wedge-tail
3485 method.|'{A3}|≡2|≡2|≡.|9|4(|πSolution by G. Marsaglia.)
3490 Consider the ``continuous Poisson distribution''
3495 |εG(x)|4α=↓|4|¬J|ur|¬X|)|≤m|)|4e|gα_↓|gtt|gx|gα_↓|g1|4dt/|≤)
3495 (x), |πfor |εx|4|¬Q|40; |πif |εX |πhas this distribution
3503 then |"l|εX|"L |πis Poisson distributed, since
3509 |εG(x|4α+↓|41)|4α_↓|4G(x)|4α=↓|4e|gα_↓|g|≤m|≤m|gx/x*3.
3510 |πIf |ε|≤m |πis large, |εG |πis approximately
3517 normal, hence |εG|gα_↓|g1{H11}({H9}F(x){H11}){H9}
3520 |πis approximately linear, where |εF(x) |πis
3526 the normal distribution function (9). Let |εg(x)
3533 |πbe an e∃ciently computable function such that
3540 |¬G|εG|gα_↓|g1{H11}({H9}F(x){H11}){H9}|4α_↓|4g(x)|¬G|4|¬W|4|
3540 ≤e |πfor |ε|→α_↓|¬X|4|¬W|4x|4|¬W|4|¬X; |πwe can
3545 now generate Poisson deviates e∃ciently as follows:
3552 Generate a normal deviate |εX, |πand set |εY|5|¬L|5g(X),
3560 N|5|¬L|5|"lY|"L, M|5|¬L|5|"lY|4α+↓|4|f1|d32|)|"L.
3562 |πIf |¬G|εY|4α_↓|4M|¬G|4|¬Q|4|≤e, |πoutput |εN;
3566 |πotherwise output |εM|4α_↓|41 |πor |εM, |πaccording
3572 as |εG{H11}({H9}F(X){H11}){H9}|4|¬W|4M |πor not.|'
3576 !!|2This approach applies also to the binomial
3583 distribution, with |εG(x)|4α=↓|4|¬J|ur1|)p|)|4u|gx|gα_↓|g1(1
3585 |4α_↓|4u)|gn|gα_↓|gx|4du |≤)(t|4α+↓|41)/|≤)(x)|≤)(t|4α+↓|41|
3586 4α_↓|4x), |πsince |"l|εG|gα_↓|g1(U)|"L |πis binomial
3591 with parameters (|εt,|4p) |πand |εG |πis approximately
3598 normal.|'|H*?*?*?{U0}{H9L11M29}W58320#Computer Programming|9(Kn
folio 710 galley 6
3600 uth/Addison-Wesley)|9f. 710|9Answers|9g. 6a|'
3603 {A6}|≡2|≡3|≡.|9|4|πYes. The second method calculates
3608 |¬Gcos|4|ε2|≤u|¬G, |πwhere |ε|≤u |πis uniformly
3613 distributed between 0 |πand |ε|≤p/2. (|πLet |εU|4α=↓|4r|4|πc
3619 os|4|ε|≤u, V|4α=↓|4r|4|πsin|4|ε|≤u.)|'⊗|≡2|≡5|≡.|9|4|f21|d33
3621 2|)|4α=↓|4(.10101)|β2. |πIn general, the binary
3626 representation is formed by using 1 for |→|↔I,
3634 0 |πfor |→|↔i, from left to right, then su∃xing
3643 1. This technique [cf. K. D. Tocher, |εJ. Roy.
3652 Stat. Soc. |π|≡B|≡-|≡1|≡6 (1954), 49] can lead
3659 to e∃cient generation of independent bits having
3666 a given probability |εp, |πas well as the geometric
3675 and binomial distributions.|'{A3}|≡2|≡6|≡.|9|4|π(a)
3679 True, |¬K|ε|βk|4|πPr(|εN|β1|4α=↓|4k)|πPr(|εN|β2|4α=↓|4n|4α_↓
3680 |4k)|4α=↓|4e|gα_↓|g|≤m|r1|gα_↓|g|≤m|r2(|≤m|β1|4α+↓|4|≤m|β2)|
3680 gn/n*3. (|πb) False, unless |ε|≤m|β2|4α=↓|40,
3685 |πsince, e.g., |εN|β1|4α_↓|4N|β2 |πcan be negative.|'
3691 {A3}|≡2|≡7|≡.|9|4|πLet the binary representation
3695 of |εp |πbe |ε.b|β1b|β2b|β3|4.|4.|4.|4, |πand
3700 proceed as follows.|'{A3}{I3.1H}!!|2|≡B|≡1|≡.|9[Initialize.]
3703 Set |εm|5|¬L|5t, N|5|¬L|50, j|5|¬L|51. (|πDuring
3709 this algorithm, |εm |πrepresents the number of
3716 simulated uniform deviates whose relation to
3722 |εp |πis still unknown, since they match |εp
3730 |πin their leading |εj|4α_↓|41 |πbits; and |εN
3737 |πis the number of simulated deviates known to
3745 be less than |εp.)|'{A3}!!|2|π|≡B|≡2|≡.|9[Look
3750 at next colunm of bits.] Generate a random integer
3759 |εM |πwith the binomial distribution (|εm,|4|f1|d32|)).
3765 (|πNow |εM |πrepresents the number of unknown
3772 deviates which fail to match |εb|βj.) |πSet |εm|5|¬L|5m|4α_↓
3779 |4M, |πand if |εb|βj|4α=↓|41 |πset |εN|5|¬L|5N|4α+↓|4M.|'
3785 {A3}!!|2|≡B|≡3|≡.|9[|πDone?] If |εm|4α=↓|40 |πor
3789 if |ε.b|βj|βα+↓|β1b|βj|βα+↓|β2|4.|4.|4.|4α=↓|40,
3791 |πthe algorithm terminates. Otherwise, set |εj|5|¬L|5j|4α+↓|
3796 41 |πand return to step B2.|'{IC}{A3}!!|2[When
3803 |εb|βj|4α=↓|41 |πfor in_nitely many |εj, |πthe
3809 average number of iterations |εA|βt |πsatis_es|'
3815 {A9}|εA|β0|4α=↓|40;!!A|βn|4α=↓|41|4α+↓|4|f1|d32|)n|4|↔k|uc|)
3815 k|)|4|↔a|(n|d5k|)|↔sA|βk,!!|πfor|9|εn|4|¬R|41.|;
3816 {A9}|πLetting |εA(z)|4α=↓|4|¬K|4A|βnz|gn/n*3,
3818 |πwe have |εA(z)|4α=↓|4e|gz|4α_↓|41|4α+↓|4A(|f1|d32|)z)e|gz|
3820 g/|g2, |πhence |εA(z)e|gα_↓|gz|4α=↓|41|4α_↓|4e|gα_↓|gz|4α+↓|
3822 4A(|f1|d32|)z)e|gα_↓|gz|g/|g2|4α=↓|4|¬K|βk|β|¬R|β0|4(1|4α_↓|
3822 4e|gα_↓|gz|g/|g2|ik)|4α=↓|41|4α_↓|4e|gα_↓|gz|4α+↓|4|¬K|βn|β|
3822 ¬R|β1|4z|gn(|→α_↓1)|gn|gα+↓|g1/n*3|4(2|gn|4α_↓|41),
3823 |πand|'{A9}{M36}|εA|βm|4α=↓|41|4α+↓|4|↔k|uc|)k|¬R1|)|4|↔a|(n
3824 |d5k|)|↔s|4|((|→α_↓1)|gk|gα+↓|g1|d22|gk|4α_↓|41|)|4α=↓|41|4α
3824 +↓|4|(V|βn|βα+↓|β1|d2n|4α+↓|41|)|4α=↓|4|πlg|4|εn|4α+↓|4|(|≤g
3824 |d2|πln|42|)|4α+↓|4|f1|d32|)|4α+↓|4|εf|β0(n)|4α+↓|4O(n|gα_↓|
3824 g1)|'{A9}{M29}|πin the notation of exercise 5.2.2<48.]|'
3831 {A24}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨∪|4|4|∨3|∨.|∨4|∨.|∨2|'
3832 {A12}{H9L11}|5|5|≡1|≡.|9|4There are (|fN|4α_↓|4t|d5n|4α_↓|4m
3834 |)) |πways to pick |εn|4α_↓|4m |πrecords from
3841 the last |εN|4α_↓|4t; (|f|εN|4α_↓|4t|4α_↓|41|d5n|4α_↓|4m|4α_
3844 ↓|41|)) |πways to pick |εn|4α_↓|4m|4α_↓|41 |πfrom
3850 |εN|4α_↓|4t|4α_↓|41 |πafter selecting the (|εt|4α+↓|41)|πst
3855 item.|'{A3}|5|5|≡2|≡.|9|4Step S3 will never go
3861 to step S5 when the number of records ldft to
3871 be examined is equal to |εn|4α_↓|4m.|'{A24}|≡2|≡8|≡.|9|4|πWe
3877 must have |εP|βj|4α=↓|4q|βj|4α+↓|4j/k, |πwhere
3882 |εq|βj|4α+↓|4|¬K|4|¬T1/k|4α_↓|4q|βi|4|¬G|4Q|βi|4α=↓|4x|βj|βα
3882 +↓|β1|¬Y|4α=↓|4p|βj|βα+↓|β1 |πfor |ε0|4|¬E|4j|4|¬W|4k.
3885 |πTo _nd such |εq|βj, |πstart with |εq|βj |πunde_ned
3893 and|εr|βj|4α=↓|4p|βj|βα+↓|β1 |πfor |ε0|4|¬E|4j|4|¬W|4k;
3896 |πthen repeatedly do the following: Find |εi
3903 |πand |εj |πwith |εq|βi, q|βj |πunde_ned and
3910 |εr|βi|4|¬R|41/k|4|¬R|4r|βj; |πset |εq|βj|5|¬L|4r|βj,
3913 Q|βj|5|¬L|5x|βi|βα+↓|β1, r|βi|5|¬L|5r|βi|4α_↓|4(1/k|4α_↓|4r|
3914 βj), r|βj|5|¬L|51/k. [|πcf. |εElectronics Letters
3919 |π|≡1|≡0|≡, 8 (1974), 127<128.]|'{A3}|≡2|≡9|≡.|9|4Generate
3924 a random point (|εy|β1,|4.|4.|4.|4,|4y|βn) |πon
3929 the unit sphere, and let |ε|≤r|4α=↓|4{H10}|¬H{H9}|v4|¬K|4a|β
3934 ky|=|βk|g2|). |πGenerate an independent uniform
3939 deviate |εU, |πand if |ε|≤r|gn|gα+↓|g1U|4|¬W|4K{H10}|¬H{H9}|
3943 v4a|=|βk|g2y|=|βk|g2|), |πoutput (|εy|β1/|≤r,|4.|4.|4.|4,|4y
3945 |βn/|≤r); |πotherwise start over. Here |εK|g2|4α=↓|4min|¬T(|
3950 ¬K|4a|βky|=|βk|g2)|gn|gα+↓|g1/(|¬K|4a|=|βk|g2y|=|βk|g2)|4|¬G
3950 |4|¬K|4y|=|βk|g2|4α=↓|41|¬Y|4α=↓|4a|urnα_↓1|)n|)|6|πif|6|εna
3950 |βn|4|¬R|4a|β1, (|εn|4α+↓|41)/(a|β2|4α+↓|4a|βn)|gn|gα+↓|g1(a
3951 |β1a|βn/n)|gn |πotherwise.|'{A24}|5|5|≡3|≡.|9|4|πWe
3954 should not confuse ``conditional'' and ``unconditional''
3960 probabilities. The quantity |εm |πdepends randomly
3966 on the selections which took place among the
3974 _rst |εt |πelements; if |πwe take the average
3982 over all possible choices which could have occurred
3990 among these elements, we will _nd (|εn|4α_↓|4m)/(N|4α_↓|4t)
3997 |πis exactly |εn/N |πon the average. For example,
4005 consider the second element; if the _rst element
4013 was selected in the sample (this happens with
4021 probability |εn/N), |πthe second element is selected
4028 with probability (|εn|4α_↓|41)/(N|4α_↓|41); |πif
4032 the _rst element was not selected, the second
4040 is selected with probability |εn/(N|4α_↓|41).
4045 |πThe overall probability of selecting the second
4052 element is (|εn/N)(n|4α_↓|41)/(N|4α_↓|41)|4α+↓|4(1|4α_↓|4n/N
4054 )(n)/(N|4α_↓|41)|4α=↓|4n/N.|'{A3}|5|5|≡4|≡.|9|4|πFrom
4056 the algorithm,|'{A9}|εp(m,|4t|4α+↓|41)|4α=↓|4|↔a1|4α_↓|4|(n|
4058 4α_↓|4m|d2N|4α_↓|4t|)|↔sp(m,|4t)|4α+↓|4|(n|4α_↓|4(m|4α_↓|41)
4058 |d2N|4α_↓|4t|)|4p(m|4α_↓|41,|4t).|;{A9}|πThe
4060 desired formula can be proved by induction on
4068 |εt. |πIn particular, |εp(n,|4N)|4α=↓|41.|'{A3}|π|5|5|≡5|≡.|
4072 9|4In the notation of exercise 4, the probability
4080 that |εt|4α=↓|4k |πat termination is |εq|βk|4α=↓|4p(|εn,|4k)
4085 |4α_↓|4p(n,|4k|4α_↓|41)|4α=↓|4(|fk|4α_↓|41|d5n|4α_↓|41|))/(|
4085 fN|d5n|)). |πThe average is |¬K|ε|β0|β|¬E|βk|β|¬E|βN|4kq|βk|
4089 4α=↓|4(N|4α+↓|41)n/(n|4α+↓|41).|'{A3}|5|5|≡6|≡.|9|4|πSimilar
4090 ly, |¬K|ε|β0|β|¬E|βk|β|¬E|βN|4k(k|4α+↓|41)q|βk|4α=↓|4(N|4α+↓
4091 |42)(N|4α+↓|41)n/(n|4α+↓|42); |πthe variance
4094 is therefore (|εN|4α+↓|41)(N|4α_↓|4n)n/(n|4α+↓|42)(n|4α+↓|41
4096 )|g2.|'{A3}|5|5|≡7|≡.|9|4|πSuppose the choice
4100 is |ε0|4|¬W|4x|β1|4|¬W|4x|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4x|βn|
4101 4|¬E|4N. |πLet |εx|β0|4α=↓|40, x|βn|βα+↓|β1|4α=↓|4N|4α+↓|41.
4104 |πThe choice is obtained with probability |εp|4α=↓|4|≥u|β1|
4111 β|¬E|βt|β|¬E|βN|4p|βt, |πwhere|'{A9}|ε|∂p|βt|4α=↓|4|(N|4α_↓|
4113 4(t|4α_↓|41)|4α_↓|4n|4α+↓|4m|d2N|4α_↓|4(t|4α_↓|41)|)!!|∂|πfo
4113 r!!|εx|βm|4|¬W|4t|4|¬W|4x|βm|βα+↓|β1,|;{A4}|Lp|βt|4α=↓|4|(n|
4114 4α_↓|4m|d2N|4α_↓|4(t|4α_↓|41)|)|L|πfor!!|εt|4α=↓|4x|βm|βα+↓|
4114 β1.>{A9}|πThe denominator of the product |εp
4121 |πis |εN*3; |πthe numerator contains the terms
4128 |εN|4α_↓|4n, N|4α_↓|4n|4α_↓|41,|4.|4.|4.|4,|41
4130 |πfor those |εt'|πs which are not |εx'|πs, and
4138 the terms |εn,|4n|4α_↓|41,|4.|4.|4.|4,|41 |πfor
4142 those |εt'|πs which |εare x'|πs. Hence |εp|4α=↓|4(N|4α_↓|4n)
4148 *3n*3/N*3. Example|*/:|\ n|4α=↓|43, N|4α=↓|48, (x|β1,|4x|β2,|4x|
4152 β3,)|4α=↓|4(2,|43,|47); p|4α=↓|4|f5|d83|)|4|f3|d37|)|4|f2|d3
4153 6|)|4|f4|d35|)|4|f3|d34|)|4|f2|d33|)|4|f1|d32|)|4|f1|d31|).|
4153 '{A3}|5|5|≡9|≡.|9|4|πThe reservoir gets seven
4158 records: 1, 2, 3, 5, 9, 13, 16. The second, fourth,
4169 and seventh of these are selected, namely 2,
4177 5, 16.|'{A3}|≡1|≡0|≡.|9|4|πDelete step R6 and
4183 the variabbl∧l∧∧b∧bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
4184 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
4184 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
4184 bbb∧b∧b∧b∧b∧b∧b∧b∧bbb∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧
4184 b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧
4184 b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧bbl*?*?{U0}{H9L11M29
folio 715 galley 7
4184 }W|π58320#Computer Programming|9(Knuth/Addison-Wesley)|9f.
4186 715|9Answers|9g. 7a|'{A6}|≡1|≡1|≡.|9|4Arguing
4189 as in Section 1.2.10, which considers the special
4197 case |εn|4α=↓|41, |πwe see that the generating
4204 function is|'{A9}|εG(z)|4α=↓|4z|gn|↔a|(1|d2n|4α+↓|41|)|4α+↓|
4206 4|(n|d2n|4α+↓|41|)|4z|↔s|↔a|(2|d2n|4α+↓|42|)|4α+↓|4|(n|d2n|4
4206 α+↓|42|)|4z|↔s|4|¬O|4|¬O|4|¬O|4|↔a|(N|4α_↓|4n|d2N|)|4α+↓|4|(
4206 n|d2N|)|4z|↔s.|;{A9}|πThe mean is |εn|4α+↓|4|¬K|βn|β|¬W|βt|β
4210 |¬E|βN(n/t)|4α=↓|4n(1|4α+↓|4H|βN|4α_↓|4H|βn);
4211 |πthe variance is |εn(H|βN|4α_↓|4H|βn)|4α_↓|4n|g2(H|1|ur(2)|
4214 )N|)|4α_↓|4H|1|ur(2)|)n|)).|'{A3}|≡1|≡2|≡.|9|4(|πNote
4216 that |ε|≤p|gα_↓|g1|4α=↓|4(b|βtt)|4.|4.|4.|4(b|β33)(b|β22),
4218 |πso we seek an algorithm which goes from the
4227 representation of |ε|≤p |πto that for |ε|≤p|gα_↓|g1.)
4234 |πSet |εb|βj|5|¬L|5j |πfor |ε1|4|¬E|4j|4|¬E|4t.
4238 |πThen for |εj|4α=↓|42,|43,|4.|4.|4.|4,|4t (|πin
4242 this order) interchange |εb|βj|≠l|5b[a|βj]. |πFinally
4247 for |εj|4α=↓|4t,|4.|4.|4.|4,|43,|42 (|πin this
4251 order) set |εb[a|βj]|5|¬L|5b|βj. (|πThe algorithm
4256 is based on the fact that (|εa|βtt)|≤p|β1|4α=↓|4|≤p|β1{H11}(
4262 {H9}b|βtt).{H11})|'{H9}{A3}|≡1|≡3|≡.|9|4|πRenumbering
4264 the deck 0,|41,|4.|4.|4.|4,|42n|4α_↓|42, |πwe
4268 _nd |εs |πtakes |εx |πinto (|ε2x)|πmod(|ε2n|4α_↓|41),
4274 c |πtakes |εx |πinto (|εx|4α+↓|41)|πmod(|ε2n|4α_↓|41).
4279 |πWe have (|εc |πfollowed by |εs)|4α=↓|4cs|4α=↓|4sc|g2.
4285 |πTherefore any product of |εc'|πs and |εs'|πs
4292 can be transformed into the form |εs|gic|gk.
4299 |πAlso |ε2|g|≤'|g(|g2|gn|gα_↓|g1|g)|4|"o|41 |π{H11}({H9}modu
4301 lo (|ε2n|4α_↓|41){H11}){H9}; |πsince |εs|g|≤'|g(|g2|gn|gα_↓|
4304 g1|g) |πand |εc|g2|gn|gα_↓|g1 |πare the idnetity
4310 permutation, at most (|ε2n|4α_↓|41)|≤'(2n|4α_↓|41)
4314 |πarrangements are possible. (The |εexact |πnumber
4320 of di=erent arrangements is (|ε2n|4α_↓|41)k,
4325 |πwhere |εk |πis the order of 2 modulo (|ε2n|4α_↓|41).
4334 |πFor if |εs|gk|4α=↓|4c|gj, |πthen |εc|gj |π_xes
4340 the card 0, so |εs|gk|4α=↓|4c|gj|4α=↓|4|πidentity.)
4345 For further details, see |εSIAM Review |π|≡3
4352 (1961), 293<297.|'{A3}|≡1|≡4|≡.|9|4Set |εY|βj|5|¬L|5j
4356 |πfor |εt|4α_↓|4n|4|¬W|4j|4|¬E|4t. |πThen for
4360 |εj|4α=↓|4t,|4t|4α_↓|41,|4.|4.|4.|4,|4t|4α_↓|4n|4α+↓|41
4361 |πdo the following operations: Set |εk|5|¬L|5|"ljU|"L|4α+↓|4
4366 1. |πIf |εk|4|¬Q|4t|4α_↓|4n |πthen set |εX|βj|5|¬L|5Y|βk
4372 |πand |εY|βk|5|¬L|5Y|βj; |πotherwise if |εk|4α=↓|4X|βi
4377 |πfor some |εi|4|¬Q|4j (|πa symbol table algorithm
4384 could be used), then set |εX|βj|5|¬L|5Y|βi |πand
4391 |εY|βi|5|¬L|5Y|βj; |πotherwise set |εX|βj|5|¬L|5k.
4395 (|πThe idea is to let |εY|βt|βα_↓|βn|βα+↓|β1,|4.|4.|4.|4,|4Y
4400 |βj |πrepresent |εX|βt|βα_↓|βn|βα+↓|β1,|4.|4.|4.|4,|4X|βj,
4403 |πand if |εi|4|¬Q|4j |πand |εX|βi|4|¬E|4t|4α_↓|4n
4408 |πalso to let |εY|βi |πrepresent |εX[X|βi], |πin
4415 the execution of Algorithm P.)|'{A24}{H10L12}|∨S|∨E|∨C|∨T|∨I
4420 |∨O|∨N|4|4|∨3|∨.|∨5|'{A12}{H9L11}|5|5|≡1|≡.|9|4A
4422 |εb-|πary sequence, yes (cf. exercise 2); a [0,1)
4430 sequence, no (since only _nitely many values
4437 are assumed by the elements).|'{A3}|5|5|≡2|≡.|9|4It
4443 is 1-distributed and 2-distributed, but not 3-distributed
4450 (the binary number 111 never appears).|'{A3}|5|5|≡3|≡.|9|4Cf
4456 . exercise 3.2.2<17; repeat the sequence there
4463 with a period of length 27.|'{A3}|5|5|≡4|≡.|9|4The
4470 sequence begins |f1|d33|), |f2|d33|), |f2|d33|),
4475 |f1|d33|), |f1|d33|), |f1|d33|), |f1|d33|), |f2|d33|),
4480 |f2|d33|), |f2|d33|), |f2|d33|), |f2|d33|), |f2|d33|),
4485 |f2|d33|), |f2|d33|), etc. When |εn|4α=↓|41,
4490 3, 7, 15,|4.|4.|4. |πwe have |ε|≤n(n)|4α=↓|41,
4496 1, 5, 5,|4.|4.|4. |πso that |ε|≤n(2|g2|gk|gα_↓|g1|4α_↓|41)|4
4501 α=↓|4|≤n(2|g2|gk|4α_↓|41)|4α=↓|4(2|g2|gk|4α_↓|41)/3;
4502 |πhence |ε|≤n(n)/n |πoscillates between |f1|d33|)
4507 and approximately |f2|d33|), and no limit exists.
4514 So the probability is unde_ned.|'!!|2The methods
4521 of Section 4.2.4 show that a numerical value
4529 |εcan |πbe meaningfully assigned to Pr(|εU|βn|4|¬W|4|f1|d32|
4534 ))|4α=↓|4Pr (leading digit of the radix-4 representation
4541 of |εn|4α+↓|41 |πis 1)|4α=↓|4log|β4|42|4α=↓|4|f1|d32|).|'
4545 {A3}|5|5|≡5|≡.|9|4If |ε|≤n|β1(n), |≤n|β2(n),
4548 |≤n|β3(n), |≤n|β4(n) |πare the counts corresponding
4554 to the four probabilities, we have |ε|≤n|β1(n)|4α+↓|4|≤n|β2(
4560 n)|4α=↓|4|≤n|β3(n)|4α+↓|4|≤n|β4(n) |πfor all
4563 |εn. |πSo the desired result follows by addition
4571 of limits.|'{A3}|5|5|≡6|≡.|9|4|πBy exercise 5
4576 and induction,|'{A9}Pr(|εS|βj(n)|6|πfor|6some|6|εj,|61|4|¬E|
4578 4j|4|¬E|4k)|4α=↓|4|↔k|uc|)1|¬Ej|¬Ek|)|4|πPr{H11}({H9}|εS|βj(
4578 n){H11}){H9}.|;{A9}|πAs |εk|5|¬M|5|→|¬X, |πthe
4582 latter is a monotone sequence bounded by 1, so
4591 it converges; and|'{A9}Pr{H11}({H9}|εS|βj(n)|6|πfor|6some|6|
4594 εj|4|¬R|41{H11}){H9}|4|¬R|4|↔k|uc|)1|¬Ej|¬Ek|)|4|πPr|ε{H11}(
4594 {H9}S|βj(n){H11})|;{H9}|πfor all |εk. |πFor a
4600 counterexample to equality, it is not hard to
4608 arrange things so that |εS|βj(n) |πis always
4615 true for |εsome j, |πyet Pr{H11}({H9}S|βj(n){H11}){H9}|4α=↓|
4620 40 |πfor |εall j.|'{A3}|5|5|≡7|≡.|9|4|πLet |εp|βi|4α=↓|4|¬K|
4625 βj|β|¬R|β1|4|πPr{H11}({H9}|εS|βi|βj(n){H11}){H9}.
4626 |πThe result of the preceding exercise can be
4634 generalized to Pr{H11}({H9}|εS|βj(n) |πfor some
4639 |εj|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βj|β|¬R|β1|4|πPr{H11}({H9}S|
4639 βj(n){H11}){H9}, |πfor |εany |πdisjoint statements
4644 |εS|βj(n). |πSo we have 1|4α=↓|4Pr{H11}({H9}|εS|βi|βj(n)
4649 |πfor some |εi, j|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βi|β|¬R|β1|4|π
4652 Pr{H11}({H9}|εS|βi|βj(n) |πfor some |εj|4|¬R|41{H11}){H9}|4|
4655 ¬R|4|¬K|βi|β|¬R|β1|4p|βi|4α=↓|41, |πand hence
4658 Pr{H11}({H9}|εS|βi|βj(n) |πfor some |εj|4|¬R|41{H11}){H9}|4α
4661 =↓|4p|βi. |πGiven |ε|≤e|4|¬Q|40, |πlet |εI |πbe
4667 large enough so that |¬K|ε|β1|β|¬E|βi|β|¬E|βI|4p|βi|4|¬R|41|
4671 4α_↓|4|≤e. |πLet |ε|≤f|βi(N)|4α=↓|4(|πnumber
4674 of |εn |πwith |εS|βi|βj(n) |πtrue, for some |εj|4|¬R|41,
4682 1|4|¬E|4n|4|¬E|4N{H11}){H9}/N. |πWe have |¬K|ε|β1|β|¬E|βi|β|
4685 ¬E|βI|4|≤f|βi(N)|4|¬E|41, |πand for all large
4690 enough |εN, |¬K|β2|β|¬E|βi|β|¬E|βI|4|≤f|βi(N)|4|¬R|4|¬K|β2|β
4692 |¬E|βi|β|¬E|βI|4p|βi|4α_↓|4|≤e; |πhence |ε|≤f|β1(N)|4|¬E|41|
4694 4α_↓|4|≤f|β2(N)|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4|≤f|βI(N)|4|¬E|41|
4694 4α_↓|4p|β2|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4p|βI|4α+↓|4|≤e|4|¬E|41|
4694 4α_↓|4(1|4α_↓|4|≤e|4α_↓|4p|β1)|4α+↓|4|≤e|4α=↓|4p|β1|4α+↓|42|
4694 ≤e. |πThis proves Pr{H11}({H9}|εS|β1|βj(n), |πsome
4699 |εj|4|¬R|41{H11}){H9}|4|¬E|4p|β1|4α+↓|42|≤e;
4700 |πhence Pr{H11}({H9}|εS|β1|βj(n), |πsome |εj|4|¬R|41{H11}){H
4703 9}|4α=↓|4p|β1, |πand the desired result holds
4709 for |εi|4α=↓|41. |πBy symmetry of the hypotheses,
4716 it holds for any value of |εi.|'{A3}{H9}|5|5|≡8|≡.|9|4|πAdd
4724 together the probabilities for |εj,|4j|4α+↓|4d,|4j|4α+↓|42d,
4728 |4.|4.|4. |πin De_nition E.|'{A3}|5|5|≡9|≡.|E|'
4733 |uw|πlim|4sup|uc|)|εn|¬|¬M|¬X|)|4(a|βn|4α+↓|4b|βn)|4|¬E|4|uw
4733 |πlim|4sup|uc|)|εn|¬M|¬X|)|4a|βn|4α+↓|4|uw|πlim|4sup|uc|)|εn
4733 |¬M|¬X|)|4b|βn;|;{A9}|πhence we get|'{A9}|uw|πlim|4sup|uc|)|
4737 εn|¬M|¬X|)|4{H11}({H9}(y|β1|βn|4α_↓|4|≤a)|g2|4α+↓|4|¬O|4|¬O|
4737 4|¬O|4α+↓|4(y|βm|βn|4α_↓|4|≤a)|g2{H11}){H9}|4|¬E|4m|≤a|g2|4α
4737 _↓|42m|≤a|g2|4α+↓|4m|≤a|g2|4α=↓|40,|;{A9}|πand
4739 this can happen only if each (|εy|βj|βn|4α_↓|4|≤a)
4746 |πtends to zero.|'{A3}|≡1|≡0|≡.|9|4In the evaluation
4752 of the sum in Eq. (22).|'{A3}|≡1|≡1|≡.|9|4|¬D|εU|β2|βn|¬F
4759 |πis |εk-|πdistributed if |¬D|εU|βn|¬F |πis (2,|42|εk)-|πdis
4764 tributed.|'{A3}|≡1|≡2|≡.|9|4Let |εf|1(x|β1,|4.|4.|4.|4,|4x|β
4766 k)|4α=↓|41 |πif |εu|4|¬E|4|πmax(|εx|β1,|4.|4.NI*?|≡1|≡1|≡.|9|
4768 4|¬D|εU|β2|βn|¬F |πis |εk-|πdistributed if |¬D|εU|βn|¬F
4773 |πis (2,|42|εk)-|πdistributed.|'{A3}|≡1|≡2|≡.|9|4Let
4776 |εf|1(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|41 |πif |εu|4|¬E|4|πmax(
4778 |εx|β1,|4.|4.|4.|4,|4x|βk)|4|¬W|4v, f|1(x|β1,|4.|4.|4.|4,|4x
4779 |βk)|4α=↓|40 |πotherwise. Then apply Theorem
4784 B.|'{A3}|≡1|≡3|≡.|9|4Let|'{A9}{A14}|h|εp|βk|4|n|∂α=↓|4|πPr(|
4786 εU|βn|βα_↓|β1|4|¬A|4[|≤a,|4|≤b),|6U|βn|4|¬A|4[|≤a,|4|≤b),|4.
4786 |4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β2|4|¬A|4[|≤a,|4|≤b),|6U|βn|βα+
4786 ↓|βk|βα_↓|β1|4{U0}{H10L12M29}W58320#Computer
folio 717 galley 8
4787 Programming|9(Knuth/Addison-Wesley)|9f. 717|9Answers|9g.
4789 8a|'{A6}It remains to translate this into the
4797 probability that |εf|1(n)|4α_↓|4f|1(n|4α_↓|41)|4α=↓|4k.
4800 |πLet |ε|≤n|βk(n)|4α=↓|4(|πnumber of |εj|4|¬E|4n
4804 |πwith |εf|1(j)|4α_↓|4f|1(j|4α_↓|41)|4α=↓|4k{H11}){H9};
4806 |πlet |ε|≤m|βk(n)|4α=↓|4|π(number of |εj|4|¬E|4n
4810 |πwith |εU|βj |πthe beginning of a gap of length
4819 |εk|4α_↓|41); |πand let |ε|≤m(n) |πsimilarly
4824 count the number of |ε1|4|¬E|4j|4|¬E|4n |πwith
4830 |εU|βj|4|¬A|4[|≤a,|4|≤b). |πWe have|'{A8}|ε|≤n|βk(n)|4α=↓|4|
4833 ≤m|βk{L11}({H9}f|1(n){L11}),!!|≤m{H11}({H9}f|1(n){H11}){H9}|
4833 4α=↓|4n.|;{A9}|πAs |εn|5|¬M|5|→|¬X, |πand we
4838 _nd that|'{A9}|ε|≤n|βk(n)/n|4α=↓|4{H11}({H9}|≤m|βk(|1f|1(n))
4840 /f|1(n){H11}){H9}|6|¬O|6{H11}({H9}f|1(n)/|≤m(f|1(n)){H11}){H
4840 9}|5|¬M|5p|βk/p|4α=↓|4p(1|4α_↓|4p)|gk|gα_↓|g1.|;
4841 [|πWe have only made use of the fact that the
4851 sequence is (|εk|4α+↓|41)-distributed.]|'{A3}|≡1|≡4|≡.|9|4|π
4854 Let|'{A9}|εp|βk|4|∂α=↓|4|πPr(|εU|βn|6|πbegins|6a|6run|6of|6l
4855 ength|6|εk)|'{A3}|Lα=↓|4|πPr(|εU|βn|βα_↓|β1|4|¬Q|4U|βn|4|¬W|
4856 4|¬O|4|¬O|4|¬O|4|¬W|4U|βn|βα+↓|βk|βα_↓|β1|4|¬Q|4U|βn|βα+↓|βk
4856 )>{A3}|Lα=↓|4|(1|d2(k|4α+↓|42)*3|)|4{H11}|↔a{H9}|↔a|(k|4α+↓|4
4857 2|d51|)|↔s|↔a|(k|4α+↓|41|d51|)|↔s|4α_↓|4|↔a|(k|4α+↓|42|d51|)
4857 |↔s|4α_↓|4|↔a|(k|4α+↓|42|d51|)|↔s|4α+↓|41{H11}|↔s{H9}>
4858 {A3}|Lα=↓|4|(k|d2(k|4α+↓|41)*3|)|4α_↓|4|(k|4α+↓|41|d2(k|4α+↓|
4858 42)*3|)>{A9}(|πcf. exercise 3.3.2<13). Now proceed
4864 as in the previous exercise to transfer this
4872 to Pr(|εf|1(n)|4α_↓|4f|1(n|4α_↓|41)|4α=↓|4k{H11}){H9}.
4874 [We have assumed only that the sequence is (|εk|4α+↓|42)-|πd
4882 istributed.]|'{A3}|≡1|≡5|≡.|9|4For |εs, t|4|¬R|40
4886 |πlet|'{A9}|εp|βs|βt|4|∂α=↓|4|πPr(|εX|βn|βα_↓|β2|βt|βα_↓|β3|
4887 4α=↓|4X|βn|βα_↓|β2|βt|βα_↓|β2|4|=|↔6α=↓|4X|βn|βα_↓|β2|βt|βα_
4887 ↓|β1|4|=|↔6α=↓|4|¬O|4|¬O|4|¬O|4|=|↔6α=↓|4X|βn|βα_↓|β1|;
4888 {A3}|L!!!!!|πand!!|εX|βn|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4X|βn|βα+↓
4888 |βs|4|=|↔6α=↓|4X|βn|βα+↓|βs|βα+↓|β1>{A3}|Lα=↓|4(|f1|d32|))|g
4889 s|gα+↓|g2|gt|gα+↓|g3;>{A9}|πfor |εt|4|¬R|40 |πlet
4893 |εq|βt|4α=↓|4|πPr(|εX|βn|βα_↓|β2|βt|βα_↓|β2|4α=↓|4X|βn|βα_↓|
4893 β2|βt|βα_↓|β1|4|=|↔6α=↓|4|¬O|4|¬O|4|¬O|4|=|↔6α=↓|4X|βn|βα_↓|
4893 β1)|4α=↓|4(|f1|d32|))|g2|gt|gα+↓|g1. |πBy exercise
4896 7, Pr(|εX|βn |πis not beginning of a coupon set)|4α=↓|4|¬K|ε
4904 |βt|β|¬R|β0|4q|βt|4α=↓|4|f2|d33|), |πPr(|εX|βn
4906 |πis beginning of coupon set of length |εs|4α+↓|42)|4α=↓|4|¬
4913 K|βt|β|¬R|β0|4p|βs|βt|4α=↓|4|f1|d33|)(|f1|d32|))|gs|gα+↓|g1.
4913 |πNow proceed as in exercise 13.|'{A3}|≡1|≡6|≡.|9|4(|πSolut
4920 ion by R. P. Stanley.) Whenever the subsequence
4928 |εS|4α=↓|4(b|4α_↓|41), (b|4α_↓|42),|4.|4.|4.|4,|41,|40,|40,|
4929 41,|4.|4.|4.|4, (b|4α_↓|42), (b|4α_↓|41) |πappears,
4933 a coupon set must end at the right of |εS, |πsince
4944 some coupon set is completed in the _rst half
4953 of |εS. |πWe now proceed to calculate the probability
4962 that a coupon set begins at position |εn |πby
4971 manipulating the probabilities that the last
4977 prior appearance of |εS |πends at position |εn|4α_↓|41,
4985 n|4α_↓|42, |πetc., as in exercise 15.|'{A3}|≡1|≡8|≡.|9|4Proc
4991 eed as in the proof of Theorem A to calculate
5001 Pr and Pr.|'{A3}|≡2|≡1|≡.|9|4Pr(|εZ|βn|4|¬A|4M|β1,|4.|4.|4.|
5004 4,|4Z|βn|βα+↓|βk|βα_↓|β1|4|¬A|4M|βk)|4α=↓|4p(M|β1)|4.|4.|4.|
5004 4p(M|βk), |πfor all |εM|β1,|4.|4.|4.|4,|4M|βk|4|¬A|4|λ|λM.|'
5008 {A3}|≡2|≡2|≡.|9|4|πIf the sequence is |εk-|πdistributed,
5013 the limit is zero by integration and Theorem
5021 B. Conversely, note that if |εf|1(x|β1,|4.|4.|4.|4,|4x|βk)
5027 |πhas an absolutely convergent Fourier series|'
5033 {A9}|εf|1(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|↔k|uc|)α_↓|¬X|¬Wc|
5033 β1,|4.|4.|4.|4,|4c|βk|¬W|¬X|)|3a(c|β1,|4.|4.|4.|4,|4c|βk)|πe
5033 xp(|ε2|≤pi(c|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4c|βkx|βk){H11}
5033 ){H9},|;{A9}|≡1|≡9|≡.|9|4(|πSolution by T. Herzog.)
5038 Yes, e.g., the sequence |¬D|εU|β|¬l|βn|β/|β2|β|¬L|¬F
5043 |πwhen |¬D|εU|βn|¬F |πsatis_es R4 (or even its
5050 weaker version), cf. exercise 33.|'{A9}we have|'
5057 {A9}|uw|πlim|uc|)|.|εN|¬M|¬X|)|4|(1|d2N|)|4|↔k|uc|)0|¬En|¬WN
5057 |)|4f|1(U|βn,|4.|4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β1)|4α=↓|4a(0,|
5057 4.|4.|4.|4,|40)|4α+↓|4|≤e|βr,|;{A6}|πwhere|'{A6}|ε|¬G|≤e|βr|
5059 ¬G|4|¬E|4|↔k|uc|)|¬Gc|β1|¬G,|4.|4.|4.|4,|4|¬Gc|βk|¬G|¬Qr|)|3
5059 |¬Ga(c|β1,|4.|4.|4.|4,|4c|βk)|¬G,|;{A9}|πso |ε|≤e|βr
5062 |πcan be made arbitrarily small; hence this limit
5070 is equal to |εa(0,|4.|4.|4.|4,|40)|4α=↓|4|¬J|ur1|)0|)|4|¬O|4
5073 |¬O|4|¬O|4|¬J|ur1|)0|)|4f(x|β1,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.
5073 |4.|4.|4dx|βk. |πSo Eq. (8) holds for all su∃ciently
5081 smooth functions |εf. |πThe remainder of the
5088 proof shows that the function in (9) can be approximated
5098 by smooth functions to any desired accuracy.|'
5105 {A3}|≡2|≡3|≡.|9|4See |εAMM |≡7|≡5 (1968), 260<264.|'
5110 {A3}|≡2|≡4|≡.|9|4|πThis follows immediately from
5114 exercise 22.|'{A3}|≡2|≡5|≡.|9|4If the sequence
5119 is equidistributed, the denominator in Corollary
5125 S approaches |f1|d312|), and the numerator approaches
5132 the quantity in this exercise.|'{A3}|≡2|≡6|≡.|9|4See
5138 |εMath. Comp. |π|≡1|≡7 (1963), 50<54. [Consider
5144 also the following example by A. G. Waterman:
5152 Let |¬D|εU|βn|¬F |πbe an equidistributed [0,|41)
5158 sequence and |¬D|εX|βn|¬F |πan |→|¬X-distributed
5163 binary sequence. Let |εV|βn|4α=↓|4U|β|"p|β|¬H|βn|β|"P
5167 |πor 1|4α_↓|4|εU|β|"p|β|¬H|βn|β|"P |πaccording
5170 as |εX|βn |πis 0 or 1. Then |¬D|εV|βn|¬F |πis
5179 equidistributed and white, but Pr(|εV|βn|4α=↓|4V|βn|βα+↓|β1)
5183 |4α=↓|4|f1|d32|)*3 |πFurthermore let |εW|βn|4α=↓|4V|βn)|πmod
5187 1 where |¬D|ε|≤e|βn|¬F |πis any sequence that
5194 decreases monotonically to 0; then |¬D|εW|βn|¬F
5200 |πis equidistributed and white, yet Pr(|εW|βn|4|¬W|4W|βn|βα+
5205 ↓|β1)|4α=↓|4|f3|d34|).]|'{A3}|≡2|≡8|≡.|9|4|πLet
5207 |¬D|εU|βn|¬F |πbe |→|¬X-|πdistributed, and use
5212 the sequence |¬D|f1|d32|)(|εX|βn|4α+↓|4U|βn)|¬F.
5215 |πThis is 3-distributed, using the fact that
5222 |¬D|εU|βn|¬F |πis (16,|43)-distributed.|'|≡2|≡9|≡.|9|4If
5226 |εx|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βt |πis any binary
5230 number, we can consider the number |ε|≤n|urE|)x|)(n)
5237 |πof times |εX|βp|4.|4.|4.|4X|βp|βα+↓|βt|βα_↓|β1|4α=↓|4x,
5240 |πwhere |ε1|4|¬E|4p|4|¬E|4n |πand |εp |πis even.
5246 Similary, let |ε|≤n|urO|)x|)(n) |πcount the number
5252 of times when |εp |πis odd. Let |ε|≤n|urE|)x|)(n)|4α+↓|4|≤n|
5259 urO|)x|)(n). |πNow|'{A9}|ε|≤n|urE|)0|)(n)|4α=↓|4|↔k|4|≤n|urE
5261 |)0|≤⊂|≤⊂|4.|4.|4.|4|≤⊂|)(n)|4|¬V|4|↔k|4|≤n|urO|){J2}|≤⊂0{J2
5261 }|≤⊂|4.|4.|4.|4{J2}|≤⊂|)(n)|4|¬V|4|↔k|4|≤n|urE|){J2}|≤⊂{J2}|
5261 ≤⊂0|4.|4.|4.|4{J2}|≤⊂|)(n)|4|¬V|4|¬O|4|¬O|4|¬O|4|¬V|4|↔k|4|≤
5261 n|urO|){J2}|≤⊂{J2}|≤⊂{J2}|≤⊂|4.|4.|4.|40(n)|;
5262 {A9}|πwhere the |ε|≤n'|πs in these summations
5268 have |ε2k |πsubscripts, where asterisks denote
5274 summation over all |ε2|g2|gk|gα_↓|g1 |πcombinations
5279 of zeros and ones, and where ``|→|¬V'' denotes
5287 approximate equality (except for an error of
5294 at most |ε2k |πdue to end conditions). Therefore
5302 we _nd that|'{A9}{M36}|ε|(1|d2n|)|42k|≤n|urE|)0|)(n)|4α=↓|4|
5305 (1|d2n|)|4|↔a|↔k|4|≤n|β|≤⊂|β0|β|≤⊂|β|4|β.|β|4|β.|β|4|β.|β|4|
5305 β|≤⊂(n)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|↔k|4|≤n|β|≤⊂|β|≤⊂|β|≤⊂|β|
5305 4|β.|β|4|β.|β|4|β.|β|4|β0(n)|↔s|4α+↓|4|(1|d2n|)|4|↔k|uc|)|πa
5305 ll|4|εx|)|4{H11}({H9}r(x)|4α_↓|4s(x){H11}){H9}|≤n|urE|)x|)(n
5305 )|4α+↓|4O|↔a|(1|d2n|)|↔s,|'{A9}{M29}|πwhere |εx|4α=↓|4x|β1|4
5307 .|4.|4.|4x|β2|βk |πcontains |εr(x) |πzeros in
5312 odd positions and |εs(x) |πzeros in even positions.
5320 By (|ε2k)-|πdistribution, the parenthesized quantity
5325 tends to |εk(2|g2|gk|gα_↓|g1)/2|g2|gk|4α=↓|4k/2.
5328 |πThe remaining sum is clearly a maximum if |ε|≤n|urE|)x|)(n
5336 )|4α=↓|4|≤n|βx(n) |πwhen |εr(x)|4|¬Q|4s(x), |πand
5340 |ε|≤n|urE|)x|)(n)|4α=↓|40 |πwhen |εr(x)|4|¬W|4s(x).
5343 |πSo the maximum of the right-hand side becomes|'
5351 {A9}|ε|(k|d22|)|4α+↓|4|↔k|uc|)0|¬Es|¬Wr|¬Ek|)|3(r|4α_↓|4s)|↔
5351 a|(k|d5r|)|↔s|↔a|(k|d5s|)|↔s|↔h2|g2|gk|4α=↓|4|(k|d22|)|4α+↓|
5351 4k|↔a|(2k|4α_↓|41{U0}{H9L11M29}W58320#Computer
folio 720 galley 9
5352 Programming|9(Knuth/Addison-Wesley)|9f. 720|9Answers|9g.
5354 9a|'{A6}|πNow Pr(|εX|β2|βn|4α=↓|40)|4|¬E|4|πlim|4sup|ε|βn|β|
5356 ¬M|β|¬X|4|≤n|urE|)0|)(2n)/n, |πso the proof is
5361 complete. |εNote|*/:|'{A9}|\|↔k|uc|)r,s|)|4|↔a|(n|d5r|)|↔s|↔a
5363 |(n|d5s|)|↔s|πmax(|εr,|4s)|4α=↓|42n2|g2|gn|gα_↓|g2|4α+↓|4n|↔
5363 a|(2n|4α_↓|41|d5n|)|↔s;|;{A4}|↔k|uc|)r,s|)|4|↔a|(n|d5r|)|↔s|
5364 ↔a|(n|d5s|)|↔s|πmin(|εr,|4s)|4α=↓|42n2|g2|gn|gα_↓|g2|4α_↓|4n
5364 (|(2n|4α_↓|41|d5n|)|↔s.|;{A9}|π|≡3|≡0|≡.|9|4Let
5366 |εf|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk)|4α=↓|4|πsign(|εx|β1
5366 |4α_↓|4x|β2|4α+↓|4x|β3|4α_↓|4x|β4|4α+↓|4|¬O|4|¬O|4|¬O|4α_↓|4
5366 x|β2|βk). |πConstruct a directed graph with |ε2|g2|gk
5373 |πnodes labeled (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1)
5376 |πand (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1),
5378 |πwhere each |εx |πis either 0 or 1. Let there
5388 be |ε1|4α+↓|4f|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk)
5390 |πdirected arcs from (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|
5393 β1) |πto (|εO;|4x|β2,|4.|4.|4.|4,|4|εx|β2|βk),
5396 |πand |ε1|4α_↓|4f|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk)
5398 |πdirected arcs leading from (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|
5402 βk|βα_↓|β1) |πto (|εE;|4x|β2,|4.|4.|4.|4,|4x|β2|βk).
5405 |πWe _nd each node has the same number of arcs
5415 leading into it as those leading out; for example,
5424 (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1) |πhas
5426 |ε1|4α_↓|4f|1(0,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1)|4α+↓|4
5426 1|4α_↓|4f|1(1,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1)
5427 |πleading in and |ε1|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk|βα
5430 _↓|β1,|40)|4α+↓|41|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓
5430 |β1,|41) |πarcs leading out, and |εf|1(x,|4x|β1,|4.|4.|4.|4,
5435 |4x|β2|βk|βα_↓|β1)|4α=↓|4|→α_↓f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk
5435 |βα_↓|β1,|4x). |πDrop all nodes which have no
5442 paths leading either in or out, i.e., (|εE;|4x|β1,|4.|4.|4.|
5449 4,|4x|β2|βk|βα_↓|β1) |πif |εf|1(0,|4x|β1,|4.|4.|4.|4,|4x|β2|
5451 βk|βα_↓|β1)|4α=↓|4|→α+↓1, |πor (|εO;|4x|β1,|4.|4.|4.|4,|4x|β
5453 2|βk|βα_↓|β1) |πif |εf|1(1,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓
5455 |β1)|4α=↓|4|→α_↓1. |πThe resulting directed graph
5460 is seen to be connected, since we can get from
5470 any node to (|εE;|41,|40,|41,|40,|4.|4.|4.|4,|41)
5474 |πand from this to any desired node. By Theorem
5483 2.3.4.2G, there is a cyclic path traversing each
5491 arc; this path has length |ε2|g2|gk|gα+↓|g1,
5497 |πand we may assume it starts at node (|εE;|40,|4.|4.|4.|4,|
5505 40). |πConstruct the cyclic sequence with |εX|β1|4α=↓|4|¬O|4
5511 |¬O|4|¬O|4α=↓|4X|β2|βk|βα_↓|β1|4α=↓|40, |πand
5513 |εX|βn|βα+↓|β2|βk|βα_↓|β1|4α=↓|4x|β2|βk |πif
5515 the |εn|πth arc of the path is from (|εE;|4x|β1,|4.|4.|4.|4,
5523 |4x|β2|βk|βα_↓|β1) |πto (|εO;|4x|β2,|4.|4.|4.|4,|4x|β2|βk)
5526 |πor from (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1)
5529 |πto (|εE;|4x|β2,|4.|4.|4.|4,|4x|β2|βk). |πFor
5532 example, the graph for |εk|4α=↓|42 |πis shown
5539 in Fig. A<5; the arcs of the cyclic path are
5549 numbered from 1 to 32, and the cyclic sequence
5558 is (00001000110010101001101110111110)(000|4.|4.|4.).
5560 Note that Pr(|εX|β2|βn|4α=↓|40)|4α=↓|4|f11|d316|)
5563 |πin this sequence. The sequence is clearly (|ε2k)-|πdistrib
5570 uted, since each (|ε2k)-|πtuple |εx|β1x|β2|4.|4.|4.|4x|β2|βk
5574 |πoccurs |ε1|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk)|4α+↓|41|
5576 4α_↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk)|4α=↓|4|πtimes
5577 in the cycle. The fact that Pr(|εX|β2|βn|4α=↓|40)
5584 |πhas the desired value comes from the fact that
5593 the maximum value on the right-hand side in the
5602 proof of the preceding exercise has been achieved
5610 by this construction.|'{A6}{H9L11M29}|≡F|≡i|≡g|≡.|4|4|≡A|≡<|
5613 ≡5|≡.|9|4|πDirected graph for the construction
5618 in exercise 30.|;{A6}{H10L12}{H9L11}|≡3|≡1|≡.|9|4Use
5622 Algorithm W with rule |ε|λR|π|β1 selecting the
5629 entire sequence.|'!!|2|εNote|*/: |\|πFor a generalization
5635 of this type of nonrandom behavior in |εR5-|πsequences,
5643 see Jean Ville, |ε|=⊂Etude Critique de la notion
5651 de Collectif (|πParis, 1939), 55<62. Perhaps
5657 |εR6 |πis also too weak, from this standpoint.|'
5665 {A3}|≡3|≡2|≡.|9|4|πIf |ε|λR, |λR|¬S |πare computable
5670 subsequence rules, so is |ε|λR|¬C|4α=↓|4|λR|λR|¬S
5675 |πde_nes by the following functions: |εf|=|βn|¬C(|εx|β0,|4.|
5680 4.|4.|4,|4x|βn|βα_↓|β1)|4α=↓|41 |πif and only
5684 if |λR de_nes the subsequence |εx|βr|m1,|4.|4.|4.|4,|4x|βr|m
5689 k |πof |εx|β0,|4.|4.|4.|4,|4x|βn|βα_↓|β1, |πwhere
5693 |εk|4|¬R|40 |πand |ε0|4|¬E|4r|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4r
5695 |βk|4|¬W|4n |πand |εf|=|βk|¬S(|εx|βr|m1,|4.|4.|4.|4,|4x|βr|m
5697 k)|4α=↓|41.|'!!|2|πNow |¬D|εX|βn|¬F|λR|λR|¬S
5700 |πis (|¬D|εX|βn|¬F|λR)|λR|¬S. |πThe result follows
5705 immediately.|'{A3}|≡3|≡3|≡.|9|4Given |ε|≤e|4|¬Q|40,
5708 |π_ns |εN|β0 |πsuch that |εN|4|¬Q|4N|β0 |πimplies
5714 that both |¬G|ε|≤n|βr(N)/N|4α_↓|4p|¬G|4|¬W|4|≤e
5717 |πand |ε|¬G|≤n|βs(N)/N|4α_↓|4p|¬G|4|¬W|4|≤e.
5719 |πThen _nd |εN|β1 |πsuch that |εN|4|¬Q|4N|β1
5725 |πimplies that |εt|βN |πis |εr|βM |πor |εs|βM
5732 |πfor some |εM|4|¬Q|4N|β0. |πNow |εN|4|¬Q|4N|β1
5737 |πimplies that|'{A9}|ε|↔g|(|≤n|βt(N)|d2N|)|4α_↓|4p|↔g|4α=↓|4
5739 |↔g|(|≤n|βr(N|βr)|4α+↓|4|≤n|βs(N|βs)|d2N|)|4α_↓|4p|↔g|4α=↓|4
5739 |↔g|(|≤n|βr(N|βr)|4α_↓|4pN|βr|4α+↓|4|≤n|βs(N|βs)|4α_↓|4pN|βs
5739 |d2N|βr|4α+↓|4N|βs|)|↔g|'{A9}|↔g|4|(|≤n|βt(N)|d2N|)|4α_↓|4p|
5740 4|↔g|4α=↓|4|↔g|4|(|≤n|βr(N|βr)|4α+↓|4|≤n|βs(N|βs)|d2N|)|4α_↓
5740 |4p|4|↔g|4α=↓|4|↔g|4|(|≤n|βr(N|βr)|4α_↓|4pN|βr|4α+↓|4|≤n|βs(
5740 N|βs)|4α_↓|4pN|βs|d2N|βr|4α+↓|4N|βs|)|4|↔g|4|¬W|4|≤e.|;
5741 {A9}|π|≡3|≡4|≡.|9|4For example, if the binary
5746 representation of |εt |πis 1|40|ε|gb|gα_↓|g2|41|40|ga|r1|41|
5750 40|ga|r2|41|4.|4.|4.|41|40|ga|rk, |πwhere ``0|ε|ga''
5753 |πstands for a sequence of |εa |πconsecutive
5760 zeros, let the rules |λR|ε|βt |πaccept |εU|βn
5767 |πif and only if |"l|εbU|βn|βα_↓|βk|"L|4α=↓|4a|β1,|4.|4.|4.|
5771 4,|4|"lbU|βn|βα_↓|β1|"L|4α=↓|4a|βk.|'{A3}|≡3|≡5|≡.|9|4Let
5773 |εa|β0|4α=↓|4s|β0 |πand |εa|βm|βα+↓|β1|4α=↓|4|πmax|¬T|εs|βk|
5775 4|¬G|40|4|¬E|4k|4|¬W|42|ga|rm|¬Y. |πConstruct
5777 a subsequence rule that selects element |εX|βn
5784 |πif and only if |εn|4α=↓|4s|βk |πfor some |εk|4|¬W|42|ga|rm
5791 , |πwhen |εa|βm|4|¬E|4n|4|¬W|4a|βm|βα+↓|β1. |πThen
5795 lim|ε|βm|β|¬M|β|¬X|≤n(a|βm)/a|βm|4α=↓|4|f1|d32|).|'
5796 {A3}|≡3|≡6|≡.|9|4|πLet |εb |πand |εk |πbe arbitrary
5802 but _xed integers greater than 1. Let |εY|βn|4α=↓|4|"lbU|βn|
5809 "L. |πAn arbitrary in_nite subsequence |¬D|εZ|βn|¬F|4α=↓|4|¬
5814 DY|βs|mn|¬F|λR |πdetermined by algorithms |λS
5819 and |λR (as in the proof of Theorem M) corresponds
5829 in a straightforward but notationally hopeless
5835 manner to algorithms |λS|¬S,|4|λR|¬S which inspect
5841 |εX|βt,|4X|βt|βα+↓|β1,|4.|4.|4.|4, X|βt|βα+↓|βs
5843 |πand/or select |εX|βt,|4X|βt|βα+↓|β1,|4.|4.|4.|4,
5846 X|βt|βα+↓|π|βm|βi|βn|β(|ε|βk|βα_↓|β1|β,|βs|β)
5847 |πof |¬D|εX|βn|¬F |πif and only if |λS and |λR
5856 inspect and/or select |εY|βs, |πwhere |εU|βs|4α=↓|40.X|βtX|β
5861 t|βα+↓|β1|4.|4.|4.|4X|βt|βα+↓|βs. |πAlgorithms
5863 |λS|¬S and |λR|¬S determine an in_nite 1-distributed
5870 subsequence of |¬D|εX|βn|¬F |πand in fact (as
5877 in exercise 32) this subsequence is |→|¬X-distributed
5884 so it is (|εk,|41)-|πdistributed. Hence we _nd
5891 Pr(|εZ|βn|4α=↓|4a) |πand Pr(|εX|βn|4α=↓|4a) |πdi=er
5895 from 1/|εb |πby less than |ε1/2|gk.|'|Ha*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
5901
folio 722 galley 10
0 {U0}{H9L11M29}|πW58320#Computer Programming|9(Knuth/Addison-
1 Wesley)|9f. 722|9Answers|9g. 10a|'{A6}!!|2|εNote|*/:
5 |\|πThe result of this exercise is true if ``|εR6''
14 |πis replaced consistently by ``|εR4'' |πor ``|εR5'';
21 |πbut it is false if ``|εR1'' |πis used, since
30 |εX(|fn|d52|)) |πmight be identically zero.|'
35 {A3}|≡3|≡7|≡.|9|4|πFor |εn|4|¬R|42 |πreplace
38 |εU|βn|l2 |πby |f1|d32|)(|εU|βn|l2|4α+↓|4|≤d|βn),
41 |πwhere |ε|≤d|βn|4α=↓|40 |πor 1 according as
47 |¬T|εU|β(|βn|βα_↓|β1|β)|l2|βα+↓|β1,|4.|4.|4.|4,|4U|βn|l2|βα_
47 ↓|β1|¬Y |πcontains an even or odd number of elements
56 less than |f1|d32|). [|εAdvances in Math. |π|≡1|≡4
63 (1974), 333<334.]|'{A3}|≡3|≡9|≡.|9|4|πSee |εActa
67 Arithmetica |π|≡2|≡1 (1972), 45<50. The best
73 possible value of |εc |πis unknown.|'{A3}|≡4|≡0|≡.|9|4If
80 every one-digit change to a random table yields
88 a random table, all tables are random (or none
97 are). If we don't allow degrees of randomness,
105 the answer must therefore be, ``Not always.''|'
112 {A24}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|∨3|∨.|∨6|'
113 {A12}{H9L11}|5|5|≡1|≡.|9|4|¬r|¬a|¬n|¬d|¬i!|h|∂|¬i|¬n|¬c|¬a!|
113 ∂|¬x|¬r|¬a|¬n|¬d!!!!!!|∂rA|5|¬L|5(|εaX|4α+↓|4c)|πmod|4|εm.|E
113 |n|'|L|π|¬s|¬t|¬j|L|¬9|¬f|Lstore|6exit|6location.>
115 |L|¬s|¬t|¬a|L|¬8|¬f|LStore|6value|6of|6|εk.>|L|¬l|¬d|¬a|L|¬x
116 |¬r|¬a|¬n|¬d|LrA|5|¬L|5|εX.>|L|π|¬m|¬u|¬l|L|¬7|¬f|LrAX|5|¬L|
117 5|εaX.>|L|π|¬s|¬l|¬a|¬x|L|¬5|LrA|5|¬L|5(|εaX)|πmod|4|εm.>
119 |L|π|¬i|¬n|¬c|¬a|L|¬1|LrA|5|¬L|5(|εaX|4α+↓|4c)|πmod|4|εm.>
120 |L|π|¬s|¬t|¬a|L|¬x|¬r|¬a|¬n|¬d|LStore|6|εX.>|h!!|2|∂|π|¬x|¬r
121 |¬a|¬n|¬d!|∂|¬j|¬n|¬o|¬v!|∂|¬3|¬1|¬4|¬1|¬5|¬9|¬2|¬6|¬2|¬1!!|
121 9|∂Add|61,|6so|61|4|¬E|4|εY|4|¬E|4k.|E|n|'|L|L|π|¬m|¬u|¬l|L|
122 ¬8|¬f|LrA|5|¬L|5|"l|εkX/m|"L.>|L|L|π|¬i|¬n|¬c|¬a|L|¬1|LAdd|6
123 1,|6so|6|ε1|4|¬E|4|εY|4|¬Ek.>|L|π|¬9|¬h|L|¬j|¬n|¬o|¬v|L|≤α/↓
124 |LReturn.>|L|L|¬j|¬m|¬p|L|≤α/↓|9|¬1>|L|¬x|¬r|¬a|¬n|¬d|L|¬c|¬
126 o|¬n|L|¬1|LValue|6of|6|εX;|6X|β0|4α=↓|41.>|π|L|¬8|¬h|L|¬c|¬o
127 |¬n|L|¬0|LTemp|6storage|6of|6|εk.>|L|π|¬7|¬h|L|¬c|¬o|¬n|L|¬3
128 |¬1|¬4|¬1|¬5|¬9|¬2|¬6|¬2|¬1|LMultiplier,|7|εa.>
129 {A3}|5|5|≡2|≡.|9|4|πPutting a random-number generator
133 into a program makes the results essentially
140 unpredictable to the programmer. If the behavior
147 of the machine on each problem were known in
156 advance, few programs would ever be written.
163 As Turing has said, the actions of a computer
172 quite often |εdo |πsurprise the programmer, especially
179 when he is debugging his program.|'{A24}{H10L12}|∨S|∨E|∨C|∨T
185 |∨I|∨O|∨N|4|4|∨4|∨.|∨1|'{A12}{H9L11}|5|5|≡1|≡.|9|41010,
187 1011, 1000,|4.|4.|4.|4,|411000, 11001, 11110.|'
191 {A3}|5|5|≡2|≡.|9|4(a)|9|→α_↓110001, |→α_↓11.001001001001|4.|
192 4.|4.|4, 11.0010010000111111|4.|4.|4.|4.|'!!|2(b)|911010011,
194 1101.001011001011|4.|4.|4.|4,|4111.011001000100000|4.|4.|4.
195 |4.|'!!|2(c)|5|6|=∩11111, |=∩10.011011011011|4.|4.|4.|4,
198 10.011|=∩1111|=∩1|4.|4.|4.|4.|'!!|2(d)|9|→α_↓9.4,
200 |→α_↓|4.|4.|4.|47582417582413,|4.|4.|4.|4562951413.|'
201 {A3}|5|5|≡3|≡.|9|41010113.2.|'{A3}|5|5|≡4|≡.|9|4(a)
203 Between rA and rX; (b) the remainder in rX has
213 radix point between bytes 3 and 4; the quotient
222 in rA ahs radix point one byte to the right of
233 the least signi_cant portion of the register.|'
240 {A3}|5|5|≡5|≡.|9|4It has been subtracted from
245 999|4.|4.|4.|49|4α=↓|410|ε|gp|4α_↓|41, |πinstead
247 of from 1000|4.|4.|4.|40|4α=↓|410|ε|gp.|'{A3}|5|5|≡6|≡.|9|4(
250 a) 2|gp|4α_↓|41, |→α_↓(2|gp|4α_↓|41); (|πb) |ε2|gp|gα_↓|g1|4
254 α_↓|41, |→α_↓2|gp|gα_↓|g1; (|πc) |ε2|gp|gα_↓|g1|4α_↓|41,
258 |→α_↓(2|gp|gα_↓|g1|4α_↓|41).|'{A3}|5|5|≡7|≡.|9|4|πA
260 ten's complement representation for a negative
266 number |εx |πcan be obtained by considering |ε10|gn|4α+↓|4x
274 (|πwhere |εn |πis large enough for this to be
283 positive) and extending it on the left with in_nitely
292 many nines. The nines' complement representation
298 can be obtained in the usual manner. (These two
307 representations are equal for nonterminating
312 decimals, otherwise the nines' complement representation
318 has the form .|4.|4.|4|εa|π99999|4.|4.|4. while
323 the ten's complement representation has the form
330 .|4.|4.|4(|εa|4α+↓|41)0000|4.|4.|4.|4.) |πThese
332 representations may be considered sensible if
338 we regard the value of the in_nite sum |εN|4α=↓|49|4α+↓|490|
346 4α+↓|4900|4α+↓|49000|4α+↓|4|¬O|4|¬O|4|¬O |πas
348 |→α_↓1, since |εN|4α_↓|410N|4α=↓|49.|'!!|2|πSee
352 also exercise 31, which considers |εp-|πadic
358 number systems. The latter agree with the |εp'|πs
366 complement notations considered here, for numbers
372 whose radix-|εp |πrepresentation is terminationg,
377 but there is no simple relation between the _eld
386 of |εp-|πadic numbers and the _eld of real numbers.|'
395 {A3}|5|5|≡8|≡.|9|4|¬K|ε|βj|4a|βjb|gj|4α=↓|4|¬K|βj|4(a|βk|βj|
395 βα+↓|βk|βα_↓|β1b|gk|gα_↓|g1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|βk|β
395 j)b|gk|gj.|'{A3}|5|5|≡9|≡.|9|4|¬a |¬b|¬a|¬d |¬a|¬d|¬o|¬b|¬e
399 |¬f|¬a|¬c|¬a|¬d|¬e |¬f|¬a|¬d|¬e|¬d. (|εNote|*/:
402 |\|πOther possible ``number sentences'' would
407 be |¬d|¬o |¬a |¬d|¬e|¬e|¬d |¬a |¬d|¬e|¬c|¬a|¬d|¬e;
413 |¬a |¬c|¬a|¬d |¬f|¬e|¬d |¬a |¬b|¬a|¬b|¬e |¬b|¬e|¬e|¬f|¬,
419 |¬c|¬o|¬c|¬o|¬a|¬, |¬c|¬o|¬f|¬f|¬e|¬e; |¬b|¬o|¬b
422 |¬f|¬a|¬c|¬e|¬d |¬a |¬d|¬e|¬a|¬d |¬d|¬o|¬d|¬o.)|'
426 |Hβ*?*?*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
426